深入淺析React中diff算法

更新時(shí)間：2021年05月18日 16:57:03 作者：WindrunnerMax

React 最為核心的就是 Virtual DOM 和 Diff 算法，diff算法的基礎(chǔ)是Virtual DOM，接下來(lái)通過本文給大家介紹React中diff算法的相關(guān)知識(shí)，對(duì)React中diff算法感興趣的朋友跟隨小編一起學(xué)習(xí)下吧

React中diff算法的理解

diff算法用來(lái)計(jì)算出Virtual DOM中改變的部分，然后針對(duì)該部分進(jìn)行DOM操作，而不用重新渲染整個(gè)頁(yè)面，渲染整個(gè)DOM結(jié)構(gòu)的過程中開銷是很大的，需要瀏覽器對(duì)DOM結(jié)構(gòu)進(jìn)行重繪與回流，而diff算法能夠使得操作過程中只更新修改的那部分DOM結(jié)構(gòu)而不更新整個(gè)DOM，這樣能夠最小化操作DOM結(jié)構(gòu)，能夠最大程度上減少瀏覽器重繪與回流的規(guī)模。

虛擬DOM

diff算法的基礎(chǔ)是Virtual DOM，Virtual DOM是一棵以JavaScript對(duì)象作為基礎(chǔ)的樹，在React中通常是通過JSX編譯而成的，每一個(gè)節(jié)點(diǎn)稱為VNode，用對(duì)象屬性來(lái)描述節(jié)點(diǎn)，實(shí)際上它是一層對(duì)真實(shí)DOM的抽象，最終可以通過渲染操作使這棵樹映射到真實(shí)環(huán)境上，簡(jiǎn)單來(lái)說(shuō)Virtual DOM就是一個(gè)Js對(duì)象，用以描述整個(gè)文檔。
在瀏覽器中構(gòu)建頁(yè)面時(shí)需要使用DOM節(jié)點(diǎn)描述整個(gè)文檔。

<div class="root" name="root">
    <p>1</p>
    <div>11</div>
</div>

如果使用Js對(duì)象去描述上述的節(jié)點(diǎn)以及文檔，那么便類似于下面的樣子，當(dāng)然這不是React中用以描述節(jié)點(diǎn)的對(duì)象，React中創(chuàng)建一個(gè)React元素的相關(guān)源碼在react/src/ReactElement.js中，文中的React版本是16.10.2。

{
    type: "div",
    props: {
        className: "root"
        name: "root",
        children: [{
            type: "p",
            props: {
                children: [{
                    type: "text",
                    props: {
                        text: "1"
                    }
                    
                }]
            }    
        },{
            type: "div",
            props: {
                children: [{
                    type: "text",
                    props: {
                        text: "11"
                    }
                }]
            }
        }]
    }
}

實(shí)際上在React16中啟用了全新的架構(gòu)Fiber，Fiber核心是實(shí)現(xiàn)了一個(gè)基于優(yōu)先級(jí)和requestIdleCallback的循環(huán)任務(wù)調(diào)度算法，相關(guān)問題不在文章中討論，相關(guān)的問題大致在于虛擬DOM由樹結(jié)構(gòu)轉(zhuǎn)變成鏈表結(jié)構(gòu)，原來(lái)的VDOM是一顆由上至下的樹，通過深度優(yōu)先遍歷，層層遞歸直下，然而這個(gè)深度優(yōu)先遍歷最大的毛病在于不可中斷，因此我們?cè)?code>diff + patch又或者是Mount巨大節(jié)點(diǎn)的時(shí)候，會(huì)造成較大的卡頓，React16的VDOM不再是一顆由上至下那么簡(jiǎn)單的樹，而是鏈表形式的虛擬DOM，鏈表的每一個(gè)節(jié)點(diǎn)是Fiber，而不是在16之前的虛擬DOM節(jié)點(diǎn)，每個(gè)Fiber節(jié)點(diǎn)記錄著諸多信息，以便走到某個(gè)節(jié)點(diǎn)的時(shí)候中斷，Fiber的思路是把渲染/更新過程(遞歸diff)拆分成一系列小任務(wù)，每次檢查樹上的一小部分，做完看是否還有時(shí)間繼續(xù)下一個(gè)任務(wù)，有的話繼續(xù)，沒有的話把自己掛起，主線程不忙的時(shí)候再繼續(xù)。Fiber在diff階段，做了如下的操作，實(shí)際相當(dāng)于在15的diff算法階段，做了優(yōu)先級(jí)的任務(wù)調(diào)度控制。

把可中斷的工作拆分成小任務(wù)。
對(duì)正在做的工作調(diào)整優(yōu)先次序、重做、復(fù)用上次(未完成)工作。
diff階段任務(wù)調(diào)度優(yōu)先級(jí)控制。

操作虛擬DOM與操作原生DOM的比較

在這里直接引用了尤大的話(2016-02-08年的回答，此時(shí)Vue2.0還未發(fā)布，Vue2.0于2016-10-01左右發(fā)布，Vue2.0才加入虛擬DOM)，相關(guān)鏈接為https://www.zhihu.com/question/31809713，建議結(jié)合鏈接中的問題閱讀，也可以看看問題中比較的示例，另外下面的回答也都非常的精髓。

原生 DOM 操作 vs 通過框架封裝操作

這是一個(gè)性能vs可維護(hù)性的取舍，框架的意義在于為你掩蓋底層的DOM操作，讓你用更聲明式的方式來(lái)描述你的目的，從而讓你的代碼更容易維護(hù)，沒有任何框架可以比純手動(dòng)的優(yōu)化DOM操作更快，因?yàn)榭蚣艿?code>DOM操作層需要應(yīng)對(duì)任何上層API可能產(chǎn)生的操作，它的實(shí)現(xiàn)必須是普適的，針對(duì)任何一個(gè)benchmark，我都可以寫出比任何框架更快的手動(dòng)優(yōu)化，但是那有什么意義呢?在構(gòu)建一個(gè)實(shí)際應(yīng)用的時(shí)候，你難道為每一個(gè)地方都去做手動(dòng)優(yōu)化嗎?出于可維護(hù)性的考慮，這顯然不可能，框架給你的保證是，你在不需要手動(dòng)優(yōu)化的情況下，我依然可以給你提供過得去的性能。

對(duì) React 的 Virtual DOM 的誤解

React從來(lái)沒有說(shuō)過React比原生操作DOM快，React的基本思維模式是每次有變動(dòng)就整個(gè)重新渲染整個(gè)應(yīng)用，如果沒有Virtual DOM，簡(jiǎn)單來(lái)想就是直接重置innerHTML，很多人都沒有意識(shí)到，在一個(gè)大型列表所有數(shù)據(jù)都變了的情況下，重置innerHTML其實(shí)是一個(gè)還算合理的操作，真正的問題是在全部重新渲染的思維模式下，即使只有一行數(shù)據(jù)變了，它也需要重置整個(gè)innerHTML，這時(shí)候顯然就有大量的浪費(fèi)。
我們可以比較一下innerHTML vs Virtual DOM的重繪性能消耗：

innerHTML: render html string O(template size) + 重新創(chuàng)建所有DOM元素O(DOM size)
Virtual DOM: render Virtual DOM + diff O(template size) + 必要的DOM更新O(DOM change)。

Virtual DOM render + diff顯然比渲染html字符串要慢，但是!它依然是純js層面的計(jì)算，比起后面的DOM操作來(lái)說(shuō)，依然便宜了太多，可以看到，innerHTML的總計(jì)算量不管是js計(jì)算還是DOM操作都是和整個(gè)界面的大小相關(guān)，但Virtual DOM的計(jì)算量里面，只有js計(jì)算和界面大小相關(guān)，DOM操作是和數(shù)據(jù)的變動(dòng)量相關(guān)的，前面說(shuō)了，和DOM操作比起來(lái)，js計(jì)算是極其便宜的，這才是為什么要有Virtual DOM:它保證了 1)不管你的數(shù)據(jù)變化多少，每次重繪的性能都可以接受; 2)你依然可以用類似innerHTML的思路去寫你的應(yīng)用。

MVVM vs Virtual DOM

相比起React，其他MVVM系框架比如Angular, Knockout以及Vue、Avalon采用的都是數(shù)據(jù)綁定:通過Directive/Binding對(duì)象，觀察數(shù)據(jù)變化并保留對(duì)實(shí)際DOM元素的引用，當(dāng)有數(shù)據(jù)變化時(shí)進(jìn)行對(duì)應(yīng)的操作，MVVM的變化檢查是數(shù)據(jù)層面的，而React的檢查是DOM結(jié)構(gòu)層面的，MVVM的性能也根據(jù)變動(dòng)檢測(cè)的實(shí)現(xiàn)原理有所不同: Angular的臟檢查使得任何變動(dòng)都有固定的O(watcher count)的代價(jià); Knockout/Vue/Avalon都采用了依賴收集，在js和DOM層面都是O(change):

臟檢查：scope digest O(watcher count) + 必要DOM更新O(DOM change)。
依賴收集：重新收集依賴O(data change) + 必要DOM更新 O(DOM change)。

可以看到，Angular最不效率的地方在于任何小變動(dòng)都有的和watcher數(shù)量相關(guān)的性能代價(jià)，但是!當(dāng)所有數(shù)據(jù)都變了的時(shí)候，Angular其實(shí)并不吃虧，依賴收集在初始化和數(shù)據(jù)變化的時(shí)候都需要重新收集依賴，這個(gè)代價(jià)在小量更新的時(shí)候幾乎可以忽略，但在數(shù)據(jù)量龐大的時(shí)候也會(huì)產(chǎn)生一定的消耗。
MVVM渲染列表的時(shí)候，由于每一行都有自己的數(shù)據(jù)作用域，所以通常都是每一行有一個(gè)對(duì)應(yīng)的ViewModel實(shí)例，或者是一個(gè)稍微輕量一些的利用原型繼承的scope對(duì)象，但也有一定的代價(jià)，所以MVVM列表渲染的初始化幾乎一定比React慢，因?yàn)閯?chuàng)建ViewModel / scope實(shí)例比起Virtual DOM來(lái)說(shuō)要昂貴很多，這里所有MVVM實(shí)現(xiàn)的一個(gè)共同問題就是在列表渲染的數(shù)據(jù)源變動(dòng)時(shí)，尤其是當(dāng)數(shù)據(jù)是全新的對(duì)象時(shí)，如何有效地復(fù)用已經(jīng)創(chuàng)建的ViewModel實(shí)例和DOM元素，假如沒有任何復(fù)用方面的優(yōu)化，由于數(shù)據(jù)是全新的，MVVM實(shí)際上需要銷毀之前的所有實(shí)例，重新創(chuàng)建所有實(shí)例，最后再進(jìn)行一次渲染!這就是為什么題目里鏈接的angular/knockout實(shí)現(xiàn)都相對(duì)比較慢，相比之下，React的變動(dòng)檢查由于是DOM結(jié)構(gòu)層面的，即使是全新的數(shù)據(jù)，只要最后渲染結(jié)果沒變，那么就不需要做無(wú)用功。
順道說(shuō)一句，React渲染列表的時(shí)候也需要提供key這個(gè)特殊prop，本質(zhì)上和track-by是一回事。

性能比較也要看場(chǎng)合

在比較性能的時(shí)候，要分清楚初始渲染、小量數(shù)據(jù)更新、大量數(shù)據(jù)更新這些不同的場(chǎng)合，Virtual DOM、臟檢查MVVM、數(shù)據(jù)收集MVVM在不同場(chǎng)合各有不同的表現(xiàn)和不同的優(yōu)化需求，Virtual DOM為了提升小量數(shù)據(jù)更新時(shí)的性能，也需要針對(duì)性的優(yōu)化，比如shouldComponentUpdate或是immutable data。

初始渲染：Virtual DOM > 臟檢查 >= 依賴收集。
小量數(shù)據(jù)更新：依賴收集 >> Virtual DOM + 優(yōu)化 > 臟檢查(無(wú)法優(yōu)化) > Virtual DOM無(wú)優(yōu)化。
大量數(shù)據(jù)更新：臟檢查 + 優(yōu)化 >= 依賴收集 + 優(yōu)化 > Virtual DOM(無(wú)法/無(wú)需優(yōu)化) >> MVVM無(wú)優(yōu)化。

不要天真地以為Virtual DOM就是快，diff不是免費(fèi)的，batching么MVVM也能做，而且最終patch的時(shí)候還不是要用原生API，在我看來(lái)Virtual DOM真正的價(jià)值從來(lái)都不是性能，而是它 1)為函數(shù)式的UI編程方式打開了大門; 2)可以渲染到DOM以外的backend，比如ReactNative。

總結(jié)

以上這些比較，更多的是對(duì)于框架開發(fā)研究者提供一些參考，主流的框架+合理的優(yōu)化，足以應(yīng)對(duì)絕大部分應(yīng)用的性能需求，如果是對(duì)性能有極致需求的特殊情況，其實(shí)應(yīng)該犧牲一些可維護(hù)性采取手動(dòng)優(yōu)化:比如Atom編輯器在文件渲染的實(shí)現(xiàn)上放棄了React而采用了自己實(shí)現(xiàn)的tile-based rendering; 又比如在移動(dòng)端需要DOM-pooling的虛擬滾動(dòng)，不需要考慮順序變化，可以繞過框架的內(nèi)置實(shí)現(xiàn)自己搞一個(gè)。

diff算法

React在內(nèi)存中維護(hù)一顆虛擬DOM樹，當(dāng)數(shù)據(jù)發(fā)生改變時(shí)(state & props)，會(huì)自動(dòng)的更新虛擬DOM，獲得一個(gè)新的虛擬DOM樹，然后通過Diff算法，比較新舊虛擬DOM樹，找出最小的有變化的部分，將這個(gè)變化的部分Patch加入隊(duì)列，最終批量的更新這些Patch到實(shí)際的DOM中。

時(shí)間復(fù)雜度

首先進(jìn)行一次完整的diff需要O(n^3)的時(shí)間復(fù)雜度，這是一個(gè)最小編輯距離的問題，在比較字符串的最小編輯距離時(shí)使用動(dòng)態(tài)規(guī)劃的方案需要的時(shí)間復(fù)雜度是O(mn)，但是對(duì)于DOM來(lái)說(shuō)是一個(gè)樹形結(jié)構(gòu)，而樹形結(jié)構(gòu)的最小編輯距離問題的時(shí)間復(fù)雜度在30多年的演進(jìn)中從O(m^3n^3)演進(jìn)到了O(n^3)，關(guān)于這個(gè)問題如果有興趣的話可以研究一下論文https://grfia.dlsi.ua.es/ml/algorithms/references/editsurvey_bille.pdf。
對(duì)于原本想要提高效率而引入的diff算法使用O(n^3)的時(shí)間復(fù)雜度顯然是不太合適的，如果有1000個(gè)節(jié)點(diǎn)元素將需要進(jìn)行十億次比較，這是一個(gè)昂貴的算法，所以必須有一些妥協(xié)來(lái)加快速度，對(duì)比較通過一些策略進(jìn)行簡(jiǎn)化，將時(shí)間復(fù)雜度縮小到O(n)，雖然并不是最小編輯距離，但是作為編輯距離與時(shí)間性能的綜合考量是一個(gè)比較好的解決方案，是一種比較好的折中方案。

diff策略

上邊提到的O(n)時(shí)間復(fù)雜度是通過一定策略進(jìn)行的，React文檔中提到了兩個(gè)假設(shè)：

兩個(gè)不同類型的元素將產(chǎn)生不同的樹。
通過渲染器附帶key屬性，開發(fā)者可以示意哪些子元素可能是穩(wěn)定的。

通俗點(diǎn)說(shuō)就是：

只進(jìn)行統(tǒng)一層級(jí)的比較，如果跨層級(jí)的移動(dòng)則視為創(chuàng)建和刪除操作。
如果是不同類型的元素，則認(rèn)為是創(chuàng)建了新的元素，而不會(huì)遞歸比較他們的孩子。
如果是列表元素等比較相似的內(nèi)容，可以通過key來(lái)唯一確定是移動(dòng)還是創(chuàng)建或刪除操作。

比較后會(huì)出現(xiàn)幾種情況，然后進(jìn)行相應(yīng)的操作：

此節(jié)點(diǎn)被添加或移除->添加或移除新的節(jié)點(diǎn)。
屬性被改變->舊屬性改為新屬性。
文本內(nèi)容被改變->舊內(nèi)容改為新內(nèi)容。
節(jié)點(diǎn)tag或key是否改變->改變則移除后創(chuàng)建新元素。

分析

在分析時(shí)會(huì)簡(jiǎn)單引用一下在React的源碼，起輔助作用的代碼，實(shí)際源碼是很復(fù)雜的，引用的是一部分片段幫助理解，本文的源碼TAG為16.10.2。
關(guān)于if (__DEV__){...}相關(guān)代碼實(shí)際上是為更好的開發(fā)者體驗(yàn)而編寫的，React中的友好的報(bào)錯(cuò)，render性能測(cè)試等等代碼都是寫在if (__DEV__)中的，在production build的時(shí)候，這些代碼不會(huì)被打包，因此我們可以毫無(wú)顧慮的提供專為開發(fā)者服務(wù)的代碼，React的最佳實(shí)踐之一就是在開發(fā)時(shí)使用development build，在生產(chǎn)環(huán)境使用production build，所以我們實(shí)際上可以先跳過這部分代碼，專注于理解較為核心的部分。
我們分析diff算法是從reconcileChildren開始的，之前從 setState -> enqueueSetState(UpdateQueue) -> scheduleUpdate -> performWork -> workLoop -> beginWork -> finishClassComponent -> reconcileChildren相關(guān)的部分就不過多介紹了，需要注意的是beginWork會(huì)將一個(gè)一個(gè)的Fiber來(lái)進(jìn)行diff，期間是可中斷的，因?yàn)槊看螆?zhí)行下一個(gè)Fiber的比對(duì)時(shí)，都會(huì)先判斷這一幀剩余的時(shí)間是否充足，鏈表的每一個(gè)節(jié)點(diǎn)是Fiber，而不是在16之前的虛擬DOM節(jié)點(diǎn)，每一個(gè)Fiber都有React16的diff策略采用從鏈表頭部開始比較的算法，是鏈?zhǔn)降纳疃葍?yōu)先遍歷，即已經(jīng)從樹形結(jié)構(gòu)變成了鏈表結(jié)構(gòu)，實(shí)際相當(dāng)于在15的diff算法階段，做了優(yōu)先級(jí)的任務(wù)調(diào)度控制。此外，每個(gè)Fiber都會(huì)有一個(gè)child、sibling、return三大屬性作為鏈接樹前后的指針；child作為模擬樹結(jié)構(gòu)的結(jié)構(gòu)指針；effectTag一個(gè)很有意思的標(biāo)記，用于記錄effect的類型，effect指的就是對(duì)DOM操作的方式，比如修改，刪除等操作，用于到后面進(jìn)行commit(類似數(shù)據(jù)庫(kù))；firstEffect、lastEffect等玩意是用來(lái)保存中斷前后effect的狀態(tài)，用戶中斷后恢復(fù)之前的操作以及tag用于標(biāo)記。
reconcileChildren實(shí)現(xiàn)的就是江湖上廣為流傳的Virtul DOM diff，其實(shí)際上只是一個(gè)入口函數(shù)，如果首次渲染，current空null，就通過mountChildFibers創(chuàng)建子節(jié)點(diǎn)的Fiber實(shí)例，如果不是首次渲染，就調(diào)用reconcileChildFibers去做diff，然后得出effect list。

// react-reconciler/src/ReactChildFiber.js line 1246
export function reconcileChildren(
  current: Fiber | null,
  workInProgress: Fiber,
  nextChildren: any,
  renderExpirationTime: ExpirationTime,
) {
  if (current === null) { // 首次渲染 創(chuàng)建子節(jié)點(diǎn)的`Fiber`實(shí)例
    workInProgress.child = mountChildFibers(
      workInProgress,
      null,
      nextChildren,
      renderExpirationTime,
    );
  } else { // 否則調(diào)用`reconcileChildFibers`去做`diff`
    workInProgress.child = reconcileChildFibers(
      workInProgress,
      current.child,
      nextChildren,
      renderExpirationTime,
    );
  }
}

對(duì)比一下mountChildFibers和reconcileChildFibers有什么區(qū)別，可以看出他們都是通過ChildReconciler工廠函數(shù)來(lái)的，只是傳遞的參數(shù)不同而已，這個(gè)參數(shù)叫shouldTrackSideEffects，他的作用是判斷是否要增加一些effectTag，主要是用來(lái)優(yōu)化初次渲染的，因?yàn)槌醮武秩緵]有更新操作。ChildReconciler是一個(gè)超級(jí)長(zhǎng)的工廠(包裝)函數(shù)，內(nèi)部有很多helper函數(shù)，最終返回的函數(shù)叫reconcileChildFibers，這個(gè)函數(shù)實(shí)現(xiàn)了對(duì)子fiber節(jié)點(diǎn)的reconciliation。

// react-reconciler/src/ReactChildFiber.js line 1370
export const reconcileChildFibers = ChildReconciler(true);
export const mountChildFibers = ChildReconciler(false);

function ChildReconciler(shouldTrackSideEffects) { 
  // ...
  function deleteChild(){
      // ...
  }
  function useFiber(){
      // ...
  }
  function placeChild(){
      // ...
  }
  function placeSingleChild(){
      // ...
  }
  function updateTextNode(){
      // ...
  }
  function updateElement(){
      // ...
  }
  function updatePortal(){
      // ...
  }
  function updateFragment(){
      // ...
  }
  function createChild(){
      // ...
  }
  function updateSlot(){
      // ...
  }
  function updateFromMap(){
      // ...
  }
  function warnOnInvalidKey(){
      // ...
  }
  function reconcileChildrenArray(){
      // ...
  }
  function reconcileChildrenIterator(){
      // ...
  }
  function reconcileSingleTextNode(){
      // ...
  }
  function reconcileSingleElement(){
      // ...
  }
  function reconcileSinglePortal(){
      // ...
  }
  function reconcileChildFibers(){
      // ...
  }
  return reconcileChildFibers;
}

reconcileChildFibers就是diff部分的主體代碼，相關(guān)操作都在ChildReconciler函數(shù)中，在這個(gè)函數(shù)中相關(guān)參數(shù)，returnFiber是即將diff的這層的父節(jié)點(diǎn)，currentFirstChild是當(dāng)前層的第一個(gè)Fiber節(jié)點(diǎn)，newChild是即將更新的vdom節(jié)點(diǎn)(可能是TextNode、可能是ReactElement，可能是數(shù)組)，不是Fiber節(jié)點(diǎn)。expirationTime是過期時(shí)間，這個(gè)參數(shù)是跟調(diào)度有關(guān)系的，跟diff沒有太大關(guān)系，另外需要注意的是，reconcileChildFibers 是reconcile(diff)的一層結(jié)構(gòu)。

首先看TextNode的diff，他是最簡(jiǎn)單的，對(duì)于diff TextNode會(huì)有兩種情況：

currentFirstNode是TextNode。
currentFirstNode不是TextNode。

分兩種情況原因就是為了復(fù)用節(jié)點(diǎn)，第一種情況，xxx是一個(gè)TextNode，那么就代表這這個(gè)節(jié)點(diǎn)可以復(fù)用，有復(fù)用的節(jié)點(diǎn)，對(duì)性能優(yōu)化很有幫助，既然新的child只有一個(gè)TextNode，那么復(fù)用節(jié)點(diǎn)之后，就把剩下的aaa節(jié)點(diǎn)就可以刪掉了，那么div的child就可以添加到workInProgress中去了。useFiber就是復(fù)用節(jié)點(diǎn)的方法，deleteRemainingChildren就是刪除剩余節(jié)點(diǎn)的方法，這里是從currentFirstChild.sibling開始刪除的。

if (currentFirstChild !== null && currentFirstChild.tag === HostText) {
  // We already have an existing node so let's just update it and delete
  // the rest.
  deleteRemainingChildren(returnFiber, currentFirstChild.sibling); // 刪除兄弟
  const existing = useFiber(currentFirstChild, textContent, expirationTime);
  existing.return = returnFiber;
  return existing; // 復(fù)用
}

第二種情況，xxx不是一個(gè)TextNode，那么就代表這個(gè)節(jié)點(diǎn)不能復(fù)用，所以就從currentFirstChild開始刪掉剩余的節(jié)點(diǎn)，其中createFiberFromText就是根據(jù)textContent來(lái)創(chuàng)建節(jié)點(diǎn)的方法，此外刪除節(jié)點(diǎn)不會(huì)真的從鏈表里面把節(jié)點(diǎn)刪除，只是打一個(gè)delete的tag，當(dāng)commit的時(shí)候才會(huì)真正的去刪除。

// The existing first child is not a text node so we need to create one
// and delete the existing ones.
// 創(chuàng)建新的Fiber節(jié)點(diǎn)，將舊的節(jié)點(diǎn)和舊節(jié)點(diǎn)的兄弟都刪除 
deleteRemainingChildren(returnFiber, currentFirstChild);
const created = createFiberFromText(
  textContent,
  returnFiber.mode,
  expirationTime,
);

接下來(lái)是React Element的diff，此時(shí)我們處理的是該節(jié)點(diǎn)的父節(jié)點(diǎn)只有此節(jié)點(diǎn)一個(gè)節(jié)點(diǎn)的情況，與上面TextNode的diff類似，他們的思路是一致的，先找有沒有可以復(fù)用的節(jié)點(diǎn)，如果沒有就另外創(chuàng)建一個(gè)。此時(shí)會(huì)用到上邊的兩個(gè)假設(shè)用以判斷節(jié)點(diǎn)是否可以復(fù)用，即key是否相同，節(jié)點(diǎn)類型是否相同，如果以上相同，則可以認(rèn)為這個(gè)節(jié)點(diǎn)只是變化了內(nèi)容，不需要?jiǎng)?chuàng)建新的節(jié)點(diǎn)，可以復(fù)用的。如果節(jié)點(diǎn)的類型不相同，就將節(jié)點(diǎn)從當(dāng)前節(jié)點(diǎn)開始把剩余的都刪除。在查找可復(fù)用節(jié)點(diǎn)的時(shí)候，其并不是只專注于第一個(gè)節(jié)點(diǎn)是否可復(fù)用，而是繼續(xù)在該層中循環(huán)找到一個(gè)可以復(fù)用的節(jié)點(diǎn)，最頂層的while以及底部的child = child.sibling;是為了繼續(xù)從子節(jié)點(diǎn)中找到一個(gè)key與tag相同的可復(fù)用節(jié)點(diǎn)，另外刪除節(jié)點(diǎn)不會(huì)真的從鏈表里面把節(jié)點(diǎn)刪除，只是打一個(gè)delete的tag，當(dāng)commit的時(shí)候才會(huì)真正的去刪除。

// react-reconciler/src/ReactChildFiber.js line 1132
const key = element.key;
let child = currentFirstChild;
while (child !== null) {
  // TODO: If key === null and child.key === null, then this only applies to
  // the first item in the list.
  if (child.key === key) {
    if (
      child.tag === Fragment
        ? element.type === REACT_FRAGMENT_TYPE
        : child.elementType === element.type ||
          // Keep this check inline so it only runs on the false path:
          (__DEV__
            ? isCompatibleFamilyForHotReloading(child, element)
            : false)
    ) {
      deleteRemainingChildren(returnFiber, child.sibling); // 因?yàn)楫?dāng)前節(jié)點(diǎn)是只有一個(gè)節(jié)點(diǎn)，而老的如果是有兄弟節(jié)點(diǎn)是要?jiǎng)h除的，是多余的
      const existing = useFiber(
        child,
        element.type === REACT_FRAGMENT_TYPE
          ? element.props.children
          : element.props,
        expirationTime,
      );
      existing.ref = coerceRef(returnFiber, child, element);
      existing.return = returnFiber;
      // ...
      return existing;
    } else {
      deleteRemainingChildren(returnFiber, child);
      break;
    }
  } else {
    deleteChild(returnFiber, child); // 從child開始delete
  }
  child = child.sibling; // 繼續(xù)從子節(jié)點(diǎn)中找到一個(gè)可復(fù)用的節(jié)點(diǎn)
}

接下來(lái)就是沒有找到可以復(fù)用的節(jié)點(diǎn)因而去創(chuàng)建節(jié)點(diǎn)了，對(duì)于Fragment節(jié)點(diǎn)和一般的Element節(jié)點(diǎn)創(chuàng)建的方式不同，因?yàn)?code>Fragment本來(lái)就是一個(gè)無(wú)意義的節(jié)點(diǎn)，他真正需要?jiǎng)?chuàng)建Fiber的是它的children，而不是它自己，所以createFiberFromFragment傳遞的不是element，而是element.props.children。

// react-reconciler/src/ReactChildFiber.js line 1178
if (element.type === REACT_FRAGMENT_TYPE) {
  const created = createFiberFromFragment(
    element.props.children,
    returnFiber.mode,
    expirationTime,
    element.key,
  );
  created.return = returnFiber;
  return created;
} else {
  const created = createFiberFromElement(
    element,
    returnFiber.mode,
    expirationTime,
  );
  created.ref = coerceRef(returnFiber, currentFirstChild, element);
  created.return = returnFiber;
  return created;
}

diff Array算是diff中最復(fù)雜的一部分了，做了很多的優(yōu)化，因?yàn)?code>Fiber樹是單鏈表結(jié)構(gòu)，沒有子節(jié)點(diǎn)數(shù)組這樣的數(shù)據(jù)結(jié)構(gòu)，也就沒有可以供兩端同時(shí)比較的尾部游標(biāo)，所以React的這個(gè)算法是一個(gè)簡(jiǎn)化的雙端比較法，只從頭部開始比較，在Vue2.0中的diff算法在patch時(shí)則是直接使用的雙端比較法實(shí)現(xiàn)的。
首先考慮相同位置進(jìn)行對(duì)比，這個(gè)是比較容易想到的一種方式，即在做diff的時(shí)候就可以從新舊的數(shù)組中按照索引一一對(duì)比，如果可以復(fù)用，就把這個(gè)節(jié)點(diǎn)從老的鏈表里面刪除，不能復(fù)用的話再進(jìn)行其他的復(fù)用策略。此時(shí)的newChildren數(shù)組是一個(gè)VDOM數(shù)組，所以在這里使用updateSlot包裝成newFiber。

// react-reconciler/src/ReactChildFiber.js line 756
function reconcileChildrenArray(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    newChildren: Array<*>,
    expirationTime: ExpirationTime,
  ): Fiber | null {
    // 機(jī)翻注釋
    // 這個(gè)算法不能通過兩端搜索來(lái)優(yōu)化，因?yàn)槲覀冊(cè)诠饫w上沒有反向指針。我想看看我們能用這個(gè)模型走多遠(yuǎn)。如果最終不值得權(quán)衡，我們可以稍后再添加。
    // 即使是雙端優(yōu)化，我們也希望在很少有變化的情況下進(jìn)行優(yōu)化，并強(qiáng)制進(jìn)行比較，而不是去尋找地圖。它想探索在前進(jìn)模式下首先到達(dá)那條路徑，并且只有當(dāng)我們注意到我們需要很多向前看的時(shí)候才去地圖。這不能處理反轉(zhuǎn)以及兩個(gè)結(jié)束的搜索，但這是不尋常的。此外，要使兩端優(yōu)化在Iterables上工作，我們需要復(fù)制整個(gè)集合。
    // 在第一次迭代中，我們只需在每次插入/移動(dòng)時(shí)都碰到壞情況（將所有內(nèi)容添加到映射中）。
    // 如果更改此代碼，還需要更新reconcileChildrenIterator()，它使用相同的算法。
    let oldFiber = currentFirstChild;
    let lastPlacedIndex = 0;
    let newIdx = 0;
    let nextOldFiber = null;
     // 第一個(gè)for循環(huán)，按照index一一對(duì)比，當(dāng)新老節(jié)點(diǎn)不一致時(shí)退出循環(huán)并且記錄退出時(shí)的節(jié)點(diǎn)及oldFiber節(jié)點(diǎn)
    for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
      if (oldFiber.index > newIdx) { // 位置不匹配
        nextOldFiber = oldFiber;  // 下一個(gè)即將對(duì)比的舊節(jié)點(diǎn)
        oldFiber = null; // 如果newFiber也為null(不能復(fù)用)就退出當(dāng)前一一對(duì)比的for循環(huán)
      } else {
        nextOldFiber = oldFiber.sibling; //正常的情況下 為了下輪循環(huán)，拿到兄弟節(jié)點(diǎn)下面賦值給oldFiber
      }
      // //如果節(jié)點(diǎn)可以復(fù)用(key值匹配)，就更新并且返回新節(jié)點(diǎn)，否則返回為null，代表節(jié)點(diǎn)不可以復(fù)用
      const newFiber = updateSlot( // 判斷是否可以復(fù)用節(jié)點(diǎn)
        returnFiber,
        oldFiber,
        newChildren[newIdx],
        expirationTime,
      );
      // 節(jié)點(diǎn)無(wú)法復(fù)用 跳出循環(huán)
      if (newFiber === null) { 
        // TODO: This breaks on empty slots like null children. That's
        // unfortunate because it triggers the slow path all the time. We need
        // a better way to communicate whether this was a miss or null,
        // boolean, undefined, etc.
        if (oldFiber === null) {
          oldFiber = nextOldFiber; // 記錄不可以復(fù)用的節(jié)點(diǎn)并且退出對(duì)比
        }
        break; // 退出循環(huán)
      }
      if (shouldTrackSideEffects) {
        // 沒有復(fù)用已經(jīng)存在的節(jié)點(diǎn)，就刪除掉已經(jīng)存在的節(jié)點(diǎn)
        if (oldFiber && newFiber.alternate === null) {
          // We matched the slot, but we didn't reuse the existing fiber, so we
          // need to delete the existing child.
          deleteChild(returnFiber, oldFiber);
        }
      }
      // 本次遍歷會(huì)給新增的節(jié)點(diǎn)打 插入的標(biāo)記
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      if (previousNewFiber === null) {
        // TODO: Move out of the loop. This only happens for the first run.
        resultingFirstChild = newFiber;
      } else {
        // TODO: Defer siblings if we're not at the right index for this slot.
        // I.e. if we had null values before, then we want to defer this
        // for each null value. However, we also don't want to call updateSlot
        // with the previous one.
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
      oldFiber = nextOldFiber;  // 重新給 oldFiber 賦值繼續(xù)遍歷
  }

在updateSlot方法中定義了判斷是否可以復(fù)用，對(duì)于文本節(jié)點(diǎn),如果key不為null，那么就代表老節(jié)點(diǎn)不是TextNode，而新節(jié)點(diǎn)又是TextNode，所以返回null，不能復(fù)用，反之則可以復(fù)用，調(diào)用updateTextNode方法，注意updateTextNode里面包含了首次渲染的時(shí)候的邏輯，首次渲染的時(shí)候回插入一個(gè)TextNode，而不是復(fù)用。

// react-reconciler/src/ReactChildFiber.js line 544
function updateSlot(
    returnFiber: Fiber,
    oldFiber: Fiber | null,
    newChild: any,
    expirationTime: ExpirationTime,
  ): Fiber | null {
    // Update the fiber if the keys match, otherwise return null.

    const key = oldFiber !== null ? oldFiber.key : null;

    if (typeof newChild === 'string' || typeof newChild === 'number') {
      // 對(duì)于新的節(jié)點(diǎn)如果是 string 或者 number，那么都是沒有 key 的，
      // 所有如果老的節(jié)點(diǎn)有 key 的話，就不能復(fù)用，直接返回 null。
      // 老的節(jié)點(diǎn) key 為 null 的話，代表老的節(jié)點(diǎn)是文本節(jié)點(diǎn)，就可以復(fù)用
      if (key !== null) {
        return null;
      }
      return updateTextNode(
        returnFiber,
        oldFiber,
        '' + newChild,
        expirationTime,
      );
    }

    // ...

    return null;
}

newChild是Object的時(shí)候基本上與ReactElement的diff類似，只是沒有while了，判斷key和元素的類型是否相等來(lái)判斷是否可以復(fù)用。首先判斷是否是對(duì)象，用的是typeof newChild === object&&newChild!== null，注意要加!== null，因?yàn)?code>typeof null也是object，然后通過$$typeof判斷是REACT_ELEMENT_TYPE還是REACT_PORTAL_TYPE，分別調(diào)用不同的復(fù)用邏輯，然后由于數(shù)組也是Object，所以這個(gè)if里面也有數(shù)組的復(fù)用邏輯。

// react-reconciler/src/ReactChildFiber.js line 569
if (typeof newChild === 'object' && newChild !== null) {
  switch (newChild.$$typeof) {
    case REACT_ELEMENT_TYPE: { // ReactElement 
      if (newChild.key === key) {
        if (newChild.type === REACT_FRAGMENT_TYPE) {
          return updateFragment(
            returnFiber,
            oldFiber,
            newChild.props.children,
            expirationTime,
            key,
          );
        }
        return updateElement(
          returnFiber,
          oldFiber,
          newChild,
          expirationTime,
        );
      } else {
        return null;
      }
    }
    case REACT_PORTAL_TYPE: {
      // 調(diào)用 updatePortal
      // ...
    }
  }

  if (isArray(newChild) || getIteratorFn(newChild)) {
    if (key !== null) {
      return null;
    }

    return updateFragment(
      returnFiber,
      oldFiber,
      newChild,
      expirationTime,
      null,
    );
  }
}

讓我們回到最初的遍歷，當(dāng)我們遍歷完成了之后，就會(huì)有兩種情況，即老節(jié)點(diǎn)已經(jīng)遍歷完畢，或者新節(jié)點(diǎn)已經(jīng)遍歷完畢，如果此時(shí)我們新節(jié)點(diǎn)已經(jīng)遍歷完畢，也就是沒有要更新的了，這種情況一般就是從原來(lái)的數(shù)組里面刪除了元素，那么直接把剩下的老節(jié)點(diǎn)刪除了就行了。如果老的節(jié)點(diǎn)在第一次循環(huán)的時(shí)候就被復(fù)用完了，新的節(jié)點(diǎn)還有，很有可能就是新增了節(jié)點(diǎn)的情況，那么這個(gè)時(shí)候只需要根據(jù)把剩余新的節(jié)點(diǎn)直接創(chuàng)建Fiber就行了。

// react-reconciler/src/ReactChildFiber.js line 839
// 新節(jié)點(diǎn)已經(jīng)更新完成，刪除多余的老節(jié)點(diǎn)
if (newIdx === newChildren.length) {
  // We've reached the end of the new children. We can delete the rest.
  deleteRemainingChildren(returnFiber, oldFiber);
  return resultingFirstChild;
}

// 新節(jié)點(diǎn)已經(jīng)更新完成，刪除多余的老節(jié)點(diǎn)
if (oldFiber === null) {
  // If we don't have any more existing children we can choose a fast path
  // since the rest will all be insertions.
  for (; newIdx < newChildren.length; newIdx++) {
    const newFiber = createChild(
      returnFiber,
      newChildren[newIdx],
      expirationTime,
    );
    if (newFiber === null) {
      continue;
    }
    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
    if (previousNewFiber === null) {
      // TODO: Move out of the loop. This only happens for the first run.
      resultingFirstChild = newFiber;
    } else {
      previousNewFiber.sibling = newFiber;
    }
    previousNewFiber = newFiber;
  }
  return resultingFirstChild;
}

接下來(lái)考慮移動(dòng)的情況如何進(jìn)行節(jié)點(diǎn)復(fù)用，即如果老的數(shù)組和新的數(shù)組里面都有這個(gè)元素，而且位置不相同這種情況下的復(fù)用，React把所有老數(shù)組元素按key或者是index放Map里，然后遍歷新數(shù)組，根據(jù)新數(shù)組的key或者index快速找到老數(shù)組里面是否有可復(fù)用的，元素有key就Map的鍵就存key，沒有key就存index。

// react-reconciler/src/ReactChildFiber.js line 872
// Add all children to a key map for quick lookups.
// 從oldFiber開始將已經(jīng)存在的節(jié)點(diǎn)的key或者index添加到map結(jié)構(gòu)中
const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

// Keep scanning and use the map to restore deleted items as moves.
// 剩余沒有對(duì)比的新節(jié)點(diǎn)，到舊節(jié)點(diǎn)的map中通過key或者index一一對(duì)比查看是否可以復(fù)用。
for (; newIdx < newChildren.length; newIdx++) {
  // 主要查看新舊節(jié)點(diǎn)的key或者index是否有相同的，然后再查看是否可以復(fù)用。
  const newFiber = updateFromMap(
    existingChildren,
    returnFiber,
    newIdx,
    newChildren[newIdx],
    expirationTime,
  );
  if (newFiber !== null) {
    if (shouldTrackSideEffects) {
      if (newFiber.alternate !== null) {
        // The new fiber is a work in progress, but if there exists a
        // current, that means that we reused the fiber. We need to delete
        // it from the child list so that we don't add it to the deletion
        // list.
        existingChildren.delete(  // 在map中刪除掉已經(jīng)復(fù)用的節(jié)點(diǎn)的key或者index
          newFiber.key === null ? newIdx : newFiber.key,
        );
      }
    }
    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
    // 添加newFiber到更新過的newFiber結(jié)構(gòu)中。
    if (previousNewFiber === null) {
      resultingFirstChild = newFiber;
    } else {
      previousNewFiber.sibling = newFiber;
    }
    previousNewFiber = newFiber;
  }
}

// react-reconciler/src/ReactChildFiber.js line 299
// 將舊節(jié)點(diǎn)的key或者index，舊節(jié)點(diǎn)保存到map結(jié)構(gòu)中，方便通過key或者index獲取
function mapRemainingChildren(
    returnFiber: Fiber,
    currentFirstChild: Fiber,
  ): Map<string | number, Fiber> {
    // Add the remaining children to a temporary map so that we can find them by
    // keys quickly. Implicit (null) keys get added to this set with their index
    // instead.
    const existingChildren: Map<string | number, Fiber> = new Map();

    let existingChild = currentFirstChild;
    while (existingChild !== null) {
      if (existingChild.key !== null) {
        existingChildren.set(existingChild.key, existingChild);
      } else {
        existingChildren.set(existingChild.index, existingChild);
      }
      existingChild = existingChild.sibling;
    }
    return existingChildren;
  }

至此新數(shù)組遍歷完畢，也就是同一層的diff過程完畢，我們可以把整個(gè)過程分為三個(gè)階段:

第一遍歷新數(shù)組，新老數(shù)組相同index進(jìn)行對(duì)比，通過updateSlot方法找到可以復(fù)用的節(jié)點(diǎn)，直到找到不可以復(fù)用的節(jié)點(diǎn)就退出循環(huán)。
第一遍歷完之后，刪除剩余的老節(jié)點(diǎn)，追加剩余的新節(jié)點(diǎn)的過程，如果是新節(jié)點(diǎn)已遍歷完成，就將剩余的老節(jié)點(diǎn)批量刪除;如果是老節(jié)點(diǎn)遍歷完成仍有新節(jié)點(diǎn)剩余，則將新節(jié)點(diǎn)直接插入。
把所有老數(shù)組元素按key或index放Map里，然后遍歷新數(shù)組，插入老數(shù)組的元素，這是移動(dòng)的情況。

每日一題

https://github.com/WindrunnerMax/EveryDay

參考

https://zhuanlan.zhihu.com/p/89363990
https://zhuanlan.zhihu.com/p/137251397
https://github.com/sisterAn/blog/issues/22
https://github.com/hujiulong/blog/issues/6
https://juejin.cn/post/6844904165026562056
https://www.cnblogs.com/forcheng/p/13246874.html
https://zh-hans.reactjs.org/docs/reconciliation.html
https://zxc0328.github.io/2017/09/28/react-16-source/
https://blog.csdn.net/halations/article/details/109284050
https://blog.csdn.net/susuzhe123/article/details/107890118
https://github.com/Advanced-Frontend/Daily-Interview-Question/issues/47
https://github.com/jianjiachenghub/react-deeplearn/blob/master/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/React16%E6%BA%90%E7%A0%81%E8%A7%A3%E6%9E%906-Fiber%E9%93%BE%E5%BC%8Fdiff%E7%AE%97%E6%B3%95.md