[[420540]]

一、基礎

Diff算法實現的是最小量更新虛擬DOM。這句話雖然簡短，但是涉及到了兩個核心要素：虛擬DOM、最小量更新。

1.虛擬DOM

虛擬DOM指的就是將真實的DOM樹構造為js對象的形式，從而解決瀏覽器操作真實DOM的性能問題。

例如：如下DOM與虛擬DOM之間的映射關系

2.最小量更新

Diff的用途就是在新老虛擬DOM之間找到最小更新的部分，從而將該部分對應的DOM進行更新。

二、整個流程

Diff算法真的很美，整個流程如下圖所示：

1. 首先比較一下新舊節點是不是同一個節點(可通過比較sel(選擇器)和key(唯一標識)值是不是相同)，不是同一個節點則進行暴力刪除(注：先以舊節點為基準插入新節點，然后再刪除舊節點)。
2. 若是同一個節點則需要進一步比較

完全相同，不做處理

新節點內容為文本，直接替換完事

新節點有子節點，這個時候就要仔細考慮一下了:若老節點沒有子元素，則直接清空老節點，將新節點的子元素插入即可;若老節點有子元素則就需要按照上述的更新策略老搞定了(記住更新策略，又可以吹好幾年了，666666)。

三、實戰

光說不練假把式，下面直接輸出diff算法的核心內容。

3.1 patch函數

Diff算法的入口函數，主要判斷新舊節點是不是同一個節點，然后交由不同的邏輯進行處理。

export default function patch(oldVnode, newVnode) { 
    // 判斷傳入的第一個參數，是DOM節點還是虛擬節點 
    if (oldVnode.sel === '' || oldVnode.sel === undefined) { 
        // 傳入的第一個參數是DOM節點，此時要包裝成虛擬節點 
        oldVnode = vnode(oldVnode.tagName.toLowerCase(), {}, [], undefined, oldVnode); 
    } 
 
    // 判斷oldVnode和newVnode是不是同一個節點 
    if (oldVnode.key === newVnode.key && oldVnode.sel === newVnode.sel) { 
        //是同一個節點，則進行精細化比較 
        patchVnode(oldVnode, newVnode); 
    } 
    else { 
        // 不是同一個節點，暴力插入新的，刪除舊的 
        let newVnodeElm = createElement(newVnode); 
 
        // 將新節點插入到老節點之前 
        if (oldVnode.elm.parentNode && newVnodeElm) { 
            oldVnode.elm.parentNode.insertBefore(newVnodeElm, oldVnode.elm); 
        } 
        // 刪除老節點 
        oldVnode.elm.parentNode.removeChild(oldVnode.elm); 
    } 
} 

3.2 patchVnode函數

該函數主要負責精細化比較，通過按照上述流程圖中的邏輯依次判斷屬于哪一個分支，從而采取不同的處理邏輯。(思路清晰，算法太牛了)

export default function patchVnode(oldVnode, newVnode) { 
    // 判斷新舊vnode是否是同一個對象 
    if (oldVnode === newVnode) { 
        return; 
    } 
    // 判斷vnode有沒有text屬性 
    if (newVnode.text !== undefined && (newVnode.children === undefined || newVnode.children.length === 0)) { 
        console.log('新vnode有text屬性'); 
        if (newVnode.text !== oldVnode.text) { 
            oldVnode.elm.innerText = newVnode.text; 
        } 
    } 
    else { 
        // 新vnode沒有text屬性，有children 
        console.log('新vnode沒有text屬性'); 
        // 判斷老的有沒有children 
        if (oldVnode.children !== undefined && oldVnode.children.length > 0) { 
            // 老的有children，新的也有children 
            updateChildren(oldVnode.elm, oldVnode.children, newVnode.children); 
        } 
        else { 
            // 老的沒有children，新的有children 
            // 清空老的節點的內容 
            oldVnode.elm.innerHTML = ''; 
            // 遍歷新的vnode的子節點，創建DOM，上樹 
            for (let i = 0; i < newVnode.children.length; i++) { 
                let dom = createElement(newVnode.children[i]); 
                oldVnode.elm.appendChild(dom); 
            } 
        } 
    } 
} 

3.3 updateChildren函數

核心函數，主要負責舊虛擬節點和新虛擬節點均存在子元素的情況，按照比較策略依次進行比較，最終找出子元素中變化的部分，實現最小更新。對于該部分，涉及到一些指針，如下所示：

1. 舊前指的就是更新前虛擬DOM中的頭部指針
2. 舊后指的就是更新前虛擬DOM中的尾部指針
3. 新前指的就是更新后虛擬DOM中的頭部指針
4. 新后指的就是更新后虛擬DOM中的尾部指針

按照上述的更新策略，上述舊虛擬DOM更新為新虛擬DOM的流程為：

1. 命中“新后舊前”策略，然后將信后對應的DOM節點(也就是節點1)移動到舊后節點(節點3)后面，然后舊前節點指針下移，新后節點指針上移。
2. 仍然命中“新后舊前”策略，做相同的操作，將節點2移動到舊后節點(節點3)后面，下移舊前節點，上移新后節點。
3. 命中“新前舊前”策略，DOM節點不變，舊前和新前節點均下移。
4. 跳出循環，移動結束。

export default function updateChildren(parentElm, oldCh, newCh) { 
    // 舊前 
    let oldStartIdx = 0; 
    // 新前 
    let newStartIdx = 0; 
    // 舊后 
    let oldEndIdx = oldCh.length - 1; 
    // 新后 
    let newEndIdx = newCh.length - 1; 
    // 舊前節點 
    let oldStartVnode = oldCh[0]; 
    // 舊后節點 
    let oldEndVnode = oldCh[oldEndIdx]; 
    // 新前節點 
    let newStartVnode = newCh[0]; 
    // 新后節點 
    let newEndVnode = newCh[newEndIdx]; 
 
    let keyMap = null; 
 
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { 
        // 略過已經加undefined標記的內容 
        if (oldStartVnode == null || oldCh[oldStartIdx] === undefined) { 
            oldStartVnode = oldCh[++oldStartIdx]; 
        } 
        else if (oldEndVnode == null || oldCh[oldEndIdx] === undefined) { 
            oldEndVnode = oldCh[--oldEndIdx]; 
        } 
        else if (newStartVnode == null || newCh[newStartIdx] === undefined) { 
            newStartVnode = newCh[++newStartIdx]; 
        } 
        else if (newEndVnode == null || newCh[newEndIdx] === undefined) { 
            newEndVnode = newCh[--newEndIdx]; 
        } 
        else if (checkSameVnode(oldStartVnode, newStartVnode)) { 
            // 新前與舊前 
            console.log('新前與舊前命中'); 
            patchVnode(oldStartVnode, newStartVnode); 
            oldStartVnode = oldCh[++oldStartIdx]; 
            newStartVnode = newCh[++newStartIdx]; 
        } 
        else if (checkSameVnode(oldEndVnode, newEndVnode)) { 
            // 新后和舊后 
            console.log('新后和舊后命中'); 
            patchVnode(oldEndVnode, newEndVnode); 
            oldEndVnode = oldCh[--oldEndIdx]; 
            newEndVnode = newCh[--newEndVnode]; 
        } 
        else if (checkSameVnode(oldStartVnode, newEndVnode)) { 
            console.log('新后和舊前命中'); 
            patchVnode(oldStartVnode, newEndVnode); 
            // 當新后與舊前命中的時候，此時要移動節點，移動新后指向的這個節點到老節點舊后的后面 
            parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling); 
            oldStartVnode = oldCh[++oldStartIdx]; 
            newEndVnode = newCh[--newEndIdx]; 
        } 
        else if (checkSameVnode(oldEndVnode, newStartVnode)) { 
            // 新前和舊后 
            console.log('新前和舊后命中'); 
            patchVnode(oldEndVnode, newStartVnode); 
            // 當新前和舊后命中的時候，此時要移動節點，移動新前指向的這個節點到老節點舊前的前面 
            parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm); 
            oldEndVnode = oldCh[--oldEndIdx]; 
            newStartVnode = newCh[++newStartIdx]; 
        } 
        else { 
            // 四種都沒有命中 
            // 制作keyMap一個映射對象，這樣就不用每次都遍歷老對象了 
            if (!keyMap) { 
                keyMap = {}; 
                for (let i = oldStartIdx; i <= oldEndIdx; i++) { 
                    const key = oldCh[i].key; 
                    if (key !== undefined) { 
                        keyMap[key] = i; 
                    } 
                } 
            } 
            // 尋找當前這項（newStartIdx）在keyMap中的映射的位置序號 
            const idxInOld = keyMap[newStartVnode.key]; 
            if (idxInOld === undefined) { 
                // 如果idxInOld是undefined表示踏實全新的項，此時會將該項創建為DOM節點并插入到舊前之前 
                parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm); 
            } 
            else { 
                // 如果不是undefined，則不是全新的項，則需要移動 
                const elmToMove = oldCh[idxInOld]; 
                patchVnode(elmToMove, newStartVnode); 
                // 把這項設置為undefined，表示已經處理完這項了 
                oldCh[idxInOld] = undefined; 
                // 移動 
                parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm); 
            } 
            // 指針下移，只移動新的頭 
            newStartVnode = newCh[++newStartIdx]; 
        } 
    } 
 
    // 循環結束后，處理未處理的項 
    if (newStartIdx <= newEndIdx) { 
        console.log('new還有剩余節點沒有處理，要加項，把所有剩余的節點插入到oldStartIdx之前'); 
        // 遍歷新的newCh，添加到老的沒有處理的之前 
        for (let i = newStartIdx; i <= newEndIdx; i++) { 
            // insertBefore方法可以自動識別null，如果是null就會自動排到隊尾去 
            // newCh[i]現在還沒有真正的DOM，所以要調用createElement函數變為DOM 
            parentElm.insertBefore(createElement(newCh[i]), oldCh[oldStartIdx].elm); 
        } 
    } 
    else if (oldStartIdx <= oldEndIdx) { 
        console.log('old還有剩余節點沒有處理，要刪除項'); 
        // 批量刪除oldStart和oldEnd指針之間的項 
        for (let i = oldStartIdx; i <= oldEndIdx; i++) { 
            if (oldCh[i]) { 
                parentElm.removeChild(oldCh[i].elm); 
            } 
        } 
    } 
} 

【編輯推薦】