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

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

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

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

Web UI 中 DOM 節(jié)點(diǎn)跨層級(jí)的移動(dòng)操作特別少，可以忽略不計(jì)。

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

對(duì)于同一層級(jí)的一組子節(jié)點(diǎn)，它們可以通過(guò)唯一 id 進(jìn)行區(qū)分。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Level by Level

List

Components

Batching

Sub-tree Rendering

Selective Sub-tree Rendering

oldVdom不存在時(shí)，將newVdom生成的dom添加到父元素
newVdom不存在時(shí)，將newVdom對(duì)應(yīng)index的真實(shí)dom刪除
oldVdom, newVdom 的根節(jié)點(diǎn)不一致時(shí)，直接將oldVdom替換為newVdom
若上述都不滿足，則說(shuō)明兩個(gè)vdom的根節(jié)點(diǎn)是一致的, 然后遞歸調(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對(duì)應(yīng)處于真實(shí)DOM中的第幾個(gè)子節(jié)點(diǎn)
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
}