摘要：傳統(tǒng)算法通過循環(huán)遞歸對節(jié)點進行依次對比，效率低下，算法復雜度達到，其中是樹中節(jié)點的總數(shù)。對于同一層級的一組子節(jié)點，它們可以通過唯一進行區(qū)分。當發(fā)現(xiàn)節(jié)點已經(jīng)不存在，則該節(jié)點及其子節(jié)點會被完全刪除掉，不會用于進一步的比較。

https://zhuanlan.zhihu.com/p/...

React diff 會幫助我們計算出 Virtual DOM 中真正變化的部分，并只針對該部分進行實際 DOM 操作，而非重新渲染整個頁面，從而保證了每次操作更新后頁面的高效渲染，因此 Virtual DOM 與 diff 是保證 React 性能口碑的幕后推手。

計算一棵樹形結(jié)構(gòu)轉(zhuǎn)換成另一棵樹形結(jié)構(gòu)的最少操作，是一個復雜且值得研究的問題。傳統(tǒng) diff 算法通過循環(huán)遞歸對節(jié)點進行依次對比，效率低下，算法復雜度達到 O(n3)，其中 n 是樹中節(jié)點的總數(shù)。

Web UI 中 DOM 節(jié)點跨層級的移動操作特別少，可以忽略不計。

擁有相同類的兩個組件將會生成相似的樹形結(jié)構(gòu)，擁有不同類的兩個組件將會生成不同的樹形結(jié)構(gòu)。

對于同一層級的一組子節(jié)點，它們可以通過唯一 id 進行區(qū)分。

對樹進行分層比較，兩棵樹只會對同一層次的節(jié)點進行比較。既然 DOM 節(jié)點跨層級的移動操作少到可以忽略不計，針對這一現(xiàn)象，React 通過 updateDepth 對 Virtual DOM 樹進行層級控制，只會對相同顏色方框內(nèi)的 DOM 節(jié)點進行比較，即同一個父節(jié)點下的所有子節(jié)點。當發(fā)現(xiàn)節(jié)點已經(jīng)不存在，則該節(jié)點及其子節(jié)點會被完全刪除掉，不會用于進一步的比較。這樣只需要對樹進行一次遍歷，便能完成整個 DOM 樹的比較。

由于 React 只會簡單的考慮同層級節(jié)點的位置變換，而對于不同層級的節(jié)點，只有創(chuàng)建和刪除操作。當出現(xiàn)節(jié)點跨層級移動時，并不會出現(xiàn)想象中的移動操作，而是以 A 為根節(jié)點的樹被整個重新創(chuàng)建，這是一種影響 React 性能的操作，因此 React 官方建議不要進行 DOM 節(jié)點跨層級的操作。

React 是基于組件構(gòu)建應(yīng)用的，對于組件間的比較所采取的策略也是簡潔高效。

如果是同一類型的組件，按照原策略繼續(xù)比較 virtual DOM tree。

如果不是，則將該組件判斷為 dirty component，從而替換整個組件下的所有子節(jié)點。

對于同一類型的組件，有可能其 Virtual DOM 沒有任何變化，如果能夠確切的知道這點那可以節(jié)省大量的 diff 運算時間，因此 React 允許用戶通過 shouldComponentUpdate() 來判斷該組件是否需要進行 diff。

如下圖，當 component D 改變?yōu)?component G 時，即使這兩個 component 結(jié)構(gòu)相似，一旦 React 判斷 D 和 G 是不同類型的組件，就不會比較二者的結(jié)構(gòu)，而是直接刪除 component D，重新創(chuàng)建 component G 以及其子節(jié)點。

當節(jié)點處于同一層級時，React diff 提供了三種節(jié)點操作，分別為：INSERT_MARKUP（插入）、MOVE_EXISTING（移動）和 REMOVE_NODE（刪除）。

INSERT_MARKUP，新的 component 類型不在老集合里， 即是全新的節(jié)點，需要對新節(jié)點執(zhí)行插入操作。

MOVE_EXISTING，在老集合有新 component 類型，且 element 是可更新的類型，generateComponentChildren 已調(diào)用 receiveComponent，這種情況下 prevChild=nextChild，就需要做移動操作，可以復用以前的 DOM 節(jié)點。

REMOVE_NODE，老 component 類型，在新集合里也有，但對應(yīng)的 element 不同則不能直接復用和更新，需要執(zhí)行刪除操作，或者老 component 不在新集合里的，也需要執(zhí)行刪除操作。

允許開發(fā)者對同一層級的同組子節(jié)點，添加唯一 key 進行區(qū)分，雖然只是小小的改動，性能上卻發(fā)生了翻天覆地的變化！

先對新集合的節(jié)點進行循環(huán)遍歷，for (name in nextChildren)，通過唯一 key 可以判斷新老集合中是否存在相同的節(jié)點，if (prevChild === nextChild)，如果存在相同節(jié)點，則進行移動操作，但在移動前需要將當前節(jié)點在老集合中的位置與 lastIndex 進行比較，if (child._mountIndex < lastIndex)，則進行節(jié)點移動操作，否則不執(zhí)行該操作。==這是一種順序優(yōu)化手段，lastIndex 一直在更新，表示訪問過的節(jié)點在老集合中最右的位置（即最大的位置）==，如果新集合中當前訪問的節(jié)點比 lastIndex 大，說明當前訪問節(jié)點在老集合中就比上一個節(jié)點位置靠后，則該節(jié)點不會影響其他節(jié)點的位置，因此不用添加到差異隊列中，即不執(zhí)行移動操作，只有當訪問的節(jié)點比 lastIndex 小時，才需要進行移動操作。

React 通過制定大膽的 diff 策略，將 O(n3) 復雜度的問題轉(zhuǎn)換成 O(n) 復雜度的問題；

React 通過分層求異的策略，對 tree diff 進行算法優(yōu)化；

React 通過相同類生成相似樹形結(jié)構(gòu)，不同類生成不同樹形結(jié)構(gòu)的策略，對 component diff 進行算法優(yōu)化；

React 通過設(shè)置唯一 key的策略，對 element diff 進行算法優(yōu)化；

建議，在開發(fā)組件時，保持穩(wěn)定的 DOM 結(jié)構(gòu)會有助于性能的提升；

建議，在開發(fā)過程中，盡量減少類似將最后一個節(jié)點移動到列表首部的操作，當節(jié)點數(shù)量過大或更新操作過于頻繁時，在一定程度上會影響 React 的渲染性能。

Level by Level

List

Components

Batching

Sub-tree Rendering

Selective Sub-tree Rendering

oldVdom不存在時，將newVdom生成的dom添加到父元素
newVdom不存在時，將newVdom對應(yīng)index的真實dom刪除
oldVdom, newVdom 的根節(jié)點不一致時，直接將oldVdom替換為newVdom
若上述都不滿足，則說明兩個vdom的根節(jié)點是一致的, 然后遞歸調(diào)用 diff & patch 方法

function h(type, props, ...children) {
    return {type, props, children};
}

function createElement(node) {
    if (typeof node === "string") {
        return document.createTextNode(node);
    }
    const $el = document.createElement(node.type);
    node.children
        .map(createElement)
        .forEach($el.appendChild.bind($el));
    return $el;
}

function changed(node1, node2) {
    return typeof node1 !== typeof node2 ||
        typeof node1 === "string" && node1 !== node2 ||
        node1.type !== node2.type
}

function updateElement($parent, newNode, oldNode, index = 0) {
    console.log(Array.from(arguments))
    // console.log(newNode)
    // console.log(newNode)

    if (!oldNode) {
        $parent.appendChild(
            createElement(newNode)
        );
    } else if (!newNode) {
        $parent.removeChild(
            $parent.childNodes[index]
        );
    } else if (changed(newNode, oldNode)) {
        console.log("if go changed")
        console.log(newNode, oldNode)
        $parent.replaceChild(
            createElement(newNode),
            $parent.childNodes[index]
        );
    } else if (newNode.type) {
        console.log("test if go last if")
        const newLength = newNode.children.length;
        const oldLength = oldNode.children.length;
        for (let i = 0; i < newLength || i < oldLength; i++) {
            updateElement(
                $parent.childNodes[index],
                newNode.children[i],
                oldNode.children[i],
                i
            );
        }
    }
}

// ---------------------------------------------------------------------

// let a = (
//     

//         
item 1
//         
item 2
//     
// );
//
// let b = (
//     

//         
item 1
//         
hello!
//     
// );

let a = h("ul", {}, h("li", {}, "item1"), h("li", {}, "item2"))
let b = h("ul", {}, h("li", {}, "item1"), h("li", {}, "hello!"))

const $root = document.getElementById("root");
const $reload = document.getElementById("reload");

updateElement($root, a);
$reload.addEventListener("click", () => {
    updateElement($root, b, a);
});



// 4. vdom diffs && patch
//index Virtual DOM對應(yīng)處于真實DOM中的第幾個子節(jié)點
function btsPatch(parentDomNode, oldVdom, newVdom, index=0) {
    if(!oldVdom) parentDomNode.appendChild(applyVDom(newVdom));
    if(!newVdom) { 
        if(parentDomNode.childNodes)
            parentDomNode.removeChild(parentDomNode.childNodes[index]);
    }
    if(typeof oldVdom != typeof newVdom ||
      (typeof oldVdom == "string" && oldVdom != newVdom) ||
      (typeof oldVdom == "object" && oldVdom.name != newVdom.name)
    ) {
        if(parentDomNode.childNodes && parentDomNode.childNodes[index])
            parentDomNode.removeChild(parentDomNode.childNodes[index]);
        parentDomNode.appendChild(applyVDom(newVdom));
    } else {
        if( typeof oldVdom == "object" ) {
            let count = Math.max(oldVdom.children.length, newVdom.children.length);
            if(count > 0) {
                for(let i=0; i < count; i++) {
                    btsPatch(parentDomNode.childNodes[index], oldVdom.children[i], newVdom.children[i], i);
                }
            }
        }
    }
    return // done bts or same string or no children
}