首先進(jìn)行總結(jié)
- diff算法的本質(zhì)是找出兩個(gè)對(duì)象之間的差異
- diff算法的核心是子節(jié)點(diǎn)數(shù)組對(duì)比，思路是通過(guò)首尾兩端對(duì)比
- key的作用主要是
- 決定節(jié)點(diǎn)是否可以復(fù)用
- 建立key-index的索引，主要是替代遍歷，提升性能泡一。
diff算法的作用
渲染真實(shí)DOM的開銷很大，有時(shí)候我們修改了某個(gè)數(shù)據(jù)，直接渲染到真實(shí)dom上會(huì)引起整個(gè)dom樹的重繪和重排捕虽。我們希望只更新我們修改的那一小塊dom，而不是整個(gè)dom坡脐，diff算法就幫我們實(shí)現(xiàn)了這點(diǎn)泄私。
diff算法的本質(zhì)就是：找出兩個(gè)對(duì)象之間的差異，目的是盡可能做到節(jié)點(diǎn)復(fù)用备闲。
此處說(shuō)到的對(duì)象晌端，指的其實(shí)就是vue中的virtual dom（虛擬dom樹），即使用js對(duì)象來(lái)表示頁(yè)面中的dom結(jié)構(gòu)恬砂。
真實(shí)dom與虛擬dom
如下一個(gè)真實(shí)dom節(jié)點(diǎn)：
<div id='app'>
<span id='child'>1</span>
</div>
可見咧纠，一個(gè)dom節(jié)點(diǎn)主要包含以下三個(gè)部分：
- 自身的標(biāo)簽名（div）
- 自身的屬性（id='app'）
- 子節(jié)點(diǎn)（span）
那我們?cè)趺从胘s對(duì)象結(jié)構(gòu)來(lái)表示這樣一個(gè)dom節(jié)點(diǎn)呢？如下即可：
const vnode = {
tag: 'div', // 自身的標(biāo)簽名
attts: {id:'app'}, // 自身的屬性
children: [{
tag:'span', attrs: {id:'child'}, chidlren: ['1']
}] // 自身的子節(jié)點(diǎn)
}
那么當(dāng)用戶對(duì)界面進(jìn)行操作泻骤，比如把div的id改為app2漆羔，將子節(jié)點(diǎn)span的文本子節(jié)點(diǎn)1改為2梧奢，那么我們就能得到如下vnode：
const vnode = {
tag: 'div', // 自身的標(biāo)簽名
attts: {id:'app2'}, // 自身的屬性
children: [{
tag:'span', attrs: {id:'child'}, chidlren: ['2']
}] // 自身的子節(jié)點(diǎn)
}
我們已經(jīng)提到，diff算法的本質(zhì)是找出兩個(gè)對(duì)象之間的差異演痒，目的是盡可能做到節(jié)點(diǎn)復(fù)用亲轨。那么我們運(yùn)行diff(vnode, vnode2)就能知道vnode與vnode2之間的差異為：
- div的id由app改為了app2
- span的文本子節(jié)點(diǎn)由1改為了2
知道了以上的差異部分，就能根據(jù)這些差異來(lái)進(jìn)行視圖的局部更新：
document.getElementById('app').setAttribute('id, 'app2') // id改為app2
document.getElementById('child').firstChild.textContent = '2' // 1改為2
在我們改變一個(gè)節(jié)點(diǎn)的時(shí)候鸟顺，我們其實(shí)主要改動(dòng)了以下兩部分：
- 自身的屬性（style惦蚊、class等）
- 子節(jié)點(diǎn)
那么diff算法就可以抽象為兩部分：
function diff(vnoe, newVnode) {
diffAttr(vnode.attr, newVnode.attr)
diffChildren(vnode.children, newVnode.children)
}
在vue之前的源碼中，是先用diff得到差異讯嫂，再根據(jù)差異去patch真實(shí)dom蹦锋，也就是分兩步：
- diff
- patch
但這樣性能上會(huì)有損失，因?yàn)閐iff過(guò)程中會(huì)遍歷一整個(gè)dom樹欧芽，patch的時(shí)候又會(huì)再遍歷一遍莉掂，其實(shí)這兩次遍歷可以合并成一次，也就是在diff的同時(shí)進(jìn)行patch千扔。
所以我們可以把流程改進(jìn)為：
function patchVnode(oldVnode, vnode, parentElm) {
patchAttr(oldVnode.attr, vnode.attr, parentElm)
patchChildren(parentElm, oldVnode.children, vnode.children)
}
patchAttr
function patchAttr(oldVnode={}, vnode={}, parentElm) {
each(oldVnode, (key, val) => { // 遍歷oldVnode巫湘，看newTreeAttr是否還有對(duì)應(yīng)的屬性
if (vnode[key]) {
val !== vnode[key] && setAttr(parentElm, key, vnode[key])
}
else {
parentElm.removeAttribute(key)
}
})
each(vnode, (key, val) => { // 看oldVnode是否還有對(duì)應(yīng)的屬性，沒(méi)有就新增昏鹃。
!oldVnode[key] && setAttr(parentElm, key, val)
})
}
function each(obj, fn) { // 遍歷對(duì)象
if (Object.prototype.toString.call(obj) !== '[object object]') {
console.error('只能遍歷對(duì)象尚氛！')
return
}
for (var key in obj) {
if (obj.hasOwnProperty(key)) {
var val = obj[key]
fn(key, val)
}
}
}
function setAttr(node, key, value) {
switch (key) {
case 'style':
each(value, (key, val) => {
node.style[key] = val
})
break
case 'value':
var tag = node.tag || ''
tag = tag.toLowerCase()
if (
tag === 'input' || tag === 'textarea'
) {
node.value = value
} else {
// if it is not a input or textarea, use 'setAttribute' to set
node.setAttribute(key, value)
}
break
default:
node.setAttribute(key, value)
break
}
}
該函數(shù)主要做了如下幾件事：
- 遍歷oldVnode，看newTreeAttr是否還有對(duì)應(yīng)的屬性洞渤；
- 如果有并且不相等阅嘶，則修改對(duì)應(yīng)的屬性；
- 如果沒(méi)有载迄，則直接刪除對(duì)應(yīng)的屬性讯柔；
- 遍歷oldVnode，是否還有對(duì)應(yīng)的屬性护昧，沒(méi)有就新增魂迄。
patchChildren
function patchChildren(parentElm, oldCh, newCh) {
let oldStartIdx = 0;
let oldEndIdx = oldCh.length - 1;
let oldStartVnode = oldCh[0];
let oldEndVnode = oldCh[oldEndIdx];
let newStartIdx = 0;
let newEndIdx = newCh.length - 1;
let newStartVnode = newCh[0];
let newEndVnode = newCh[newEndIdx];
let oldKeyToIdx, idxInOld, elmToMove, refElm;
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (!oldStartVnode) {
oldStartVnode = oldCh[++oldStartIdx];
} else if (!oldEndVnode) {
oldEndVnode = oldCh[--oldEndIdx];
}
else if (sameVnode(oldStartVnode, newStartVnode)) { //舊首 和 新首相同
patchVnode(oldStartVnode.elm, oldStartVnode, newStartVnode);
oldStartVnode = oldCh[++oldStartIdx];
newStartVnode = newCh[++newStartIdx];
}
else if (sameVnode(oldEndVnode, newEndVnode)) { //舊尾 和 新尾相同
patchVnode(oldEndVnode.elm, oldEndVnode, newEndVnode);
oldEndVnode = oldCh[--oldEndIdx];
newEndVnode = newCh[--newEndIdx];
}
else if (sameVnode(oldStartVnode, newEndVnode)) { //舊首 和 新尾相同,將舊首移動(dòng)到 最后面
patchVnode(oldStartVnode.elm, oldStartVnode, newEndVnode);
nodeOps.insertBefore(parentElm, oldStartVnode.elm, oldEndVnode.elm.nextSibling)//將 舊首 移動(dòng)到最后一個(gè)節(jié)點(diǎn)后面
oldStartVnode = oldCh[++oldStartIdx];
newEndVnode = newCh[--newEndIdx];
}
else if (sameVnode(oldEndVnode, newStartVnode)) {//舊尾 和 新首相同 ,將 舊尾 移動(dòng)到 最前面
patchVnode(oldEndVnode.elm, oldEndVnode, newStartVnode);
nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
oldEndVnode = oldCh[--oldEndIdx];
newStartVnode = newCh[++newStartIdx];
}
else {//首尾對(duì)比 都不 符合 sameVnode 的話
//1. 嘗試 用 newCh 的第一項(xiàng)在 oldCh 內(nèi)尋找 sameVnode
let elmToMove = oldCh[idxInOld];
if (!oldKeyToIdx) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
idxInOld = newStartVnode.key ? oldKeyToIdx[newStartVnode.key] : null;
if (!idxInOld) {//如果 oldCh 不存在 sameVnode 則直接創(chuàng)建一個(gè)
nodeOps.createElm(newStartVnode, parentElm);
newStartVnode = newCh[++newStartIdx];
} else {
elmToMove = oldCh[idxInOld];
if (sameVnode(elmToMove, newStartVnode)) {
patchVnode(elmToMove, newStartVnode);
oldCh[idxInOld] = undefined;
nodeOps.insertBefore(parentElm, newStartVnode.elm, oldStartVnode.elm);
newStartVnode = newCh[++newStartIdx];
} else {
nodeOps.createElm(newStartVnode, parentElm);
newStartVnode = newCh[++newStartIdx];
}
}
}
}
if (oldStartIdx > oldEndIdx) {
refElm = (newCh[newEndIdx + 1]) ? newCh[newEndIdx + 1].elm : null;
nodeOps.addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx);
} else if (newStartIdx > newEndIdx) {
nodeOps.removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
}
}
上述代碼的本質(zhì)是找出兩個(gè)數(shù)組的差異
比如說(shuō)：
- 舊數(shù)組
[a, b, c, d] - 新數(shù)組
[e, f, g, h]
怎么找出新舊數(shù)組之間的差異呢？可以定義以下名詞：
- 舊首（舊數(shù)組的第一個(gè)元素）
- 舊尾（舊數(shù)組的最后一個(gè)元素）
- 新首（新數(shù)組的第一個(gè)元素）
- 新尾（新數(shù)組的最后一個(gè)元素）
代碼中的一些函數(shù)工具：
- sameVnode：用于判斷字節(jié)是否應(yīng)該復(fù)用惋耙，此處做了一些簡(jiǎn)化捣炬，實(shí)際的diff算法要更復(fù)雜一些。這里只用tag和key相同我們就復(fù)用绽榛，執(zhí)行patchVnode湿酸，即對(duì)節(jié)點(diǎn)進(jìn)行修改。
function sameVnode(a, b) {
return a.key === b.key && a.tag === b.tag
}
- createKeyToOldIdx：建立key-index的索引灭美，主要是替代遍歷推溃，提升性能。
function createKeyToOldIdx(children, beginIdx, endIdx) {
let i, key
const map = {}
for (i = beginIdx; i <= endIdx; ++i) {
key = children[i].key
if (isDef(key)) map[key] = i
}
return map
}
- 舊首 和 新首 對(duì)比
if (sameVnode(oldStartVnode, newStartVnode)) {
patchVnode(oldStartVnode.elm, oldStartVnode, newStartVnode);
oldStartVnode = oldCh[++oldStartIdx];
newStartVnode = newCh[++newStartIdx];
}
- 舊尾 和 新尾 對(duì)比
if (sameVnode(oldEndVnode, newEndVnode)) { //舊尾 和 新尾相同
patchVnode(oldEndVnode.elm, oldEndVnode, newEndVnode);
oldEndVnode = oldCh[--oldEndIdx];
newEndVnode = newCh[--newEndIdx];
}
- 舊首 和 新尾 對(duì)比
if (sameVnode(oldStartVnode, newEndVnode)) { //舊首 和 新尾相同,將舊首移動(dòng)到 最后面
patchVnode(oldStartVnode.elm, oldStartVnode, newEndVnode);
nodeOps.insertBefore(parentElm, oldStartVnode.elm, oldEndVnode.elm.nextSibling)
oldStartVnode = oldCh[++oldStartIdx];
newEndVnode = newCh[--newEndIdx];
}
- 舊尾 和 新首 對(duì)比届腐；將 舊尾 移動(dòng)到最前面
if (sameVnode(oldEndVnode, newStartVnode)) {//舊尾 和 新首相同 ,將 舊尾 移動(dòng)到 最前面
patchVnode(oldEndVnode.elm, oldEndVnode, newStartVnode);
nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
oldEndVnode = oldCh[--oldEndIdx];
newStartVnode = newCh[++newStartIdx];
}
- 首位對(duì)比 都不符合 sameVnode的話
- 嘗試用newCh的第一項(xiàng)在oldCh內(nèi)尋找sameVnode铁坎，如果在oldCh不存在對(duì)應(yīng)的sameVnode蜂奸，則直接創(chuàng)建一個(gè)，存在的話則判斷硬萍；
- 符合sameVnode窝撵，則移動(dòng)oldCh對(duì)應(yīng)的節(jié)點(diǎn)；
- 不符合sameVnode襟铭，則創(chuàng)建新節(jié)點(diǎn)。
- 最后通過(guò)oldStartIdx > oldEndIex短曾，來(lái)判斷oldCh和newCh哪一個(gè)先遍歷完成
- oldCh先遍歷完成寒砖，則證明newCh還有多余的節(jié)點(diǎn)，需要新增這些節(jié)點(diǎn)嫉拐；
- newCh先遍歷完成哩都，則證明oldCh還有多余節(jié)點(diǎn)，需要刪除這些節(jié)點(diǎn)婉徘。
