react diff算法源碼解析
React中Diff算法又稱為調(diào)和算法，對(duì)應(yīng)函數(shù)名為reconcileChildren，它的主要作用是標(biāo)記更新過程中那些元素發(fā)生了變化，這些變化包括新增、移動(dòng)、刪除。過程發(fā)生在beginWork階段，只有非初次渲染才會(huì)Diff。
以前看過一些文章將Diff算法表述為兩顆Fiber樹的比較，這是不正確的，實(shí)際的Diff過程是一組現(xiàn)有的Fiber節(jié)點(diǎn)和新的由JSX生成的ReactElement的比較，然后生成新的Fiber節(jié)點(diǎn)的過程，這個(gè)過程中也會(huì)嘗試復(fù)用現(xiàn)有Fiber節(jié)點(diǎn)。
節(jié)點(diǎn)Diff又分為兩種：
- 單節(jié)點(diǎn)Diff ——
Element、Portal、string、number。 - 多節(jié)點(diǎn)Diff ——
Array、Iterator。
以下React版本為17.0.1，代碼文件為ReactChildFiber.old.js。
單節(jié)點(diǎn)Diff
單節(jié)點(diǎn)Diff比較簡單，只有key相同并且type相同的情況才會(huì)嘗試復(fù)用節(jié)點(diǎn)，否則會(huì)返回新的節(jié)點(diǎn)。
單節(jié)點(diǎn)大部分情況下我們都不會(huì)去賦值key，所以它們默認(rèn)為null，也是相同的。
reconcileSingleElement
// 單節(jié)點(diǎn)比較
function reconcileSingleElement(
returnFiber: Fiber,
currentFirstChild: Fiber | null,
element: ReactElement,
lanes: Lanes,
): Fiber {
// 當(dāng)前新的reactElement的key
const key = element.key;
// 當(dāng)前的child fiber節(jié)點(diǎn)
let child = currentFirstChild;
while (child !== null) {
// key相同的情況才diff
if (child.key === key) {
switch (child.tag) {
// ...
default: {
// 當(dāng)前fiber和reactElement的type相同時(shí)
if (child.elementType === element.type) {
// 刪除同級(jí)的其他節(jié)點(diǎn)
deleteRemainingChildren(returnFiber, child.sibling);
// 復(fù)用當(dāng)前child fiber
const existing = useFiber(child, element.props);
existing.ref = coerceRef(returnFiber, child, element);
existing.return = returnFiber;
// 返回可復(fù)用的child fiber
return existing;
}
break;
}
}
// 不匹配刪除節(jié)點(diǎn)
deleteRemainingChildren(returnFiber, child);
break;
} else {
// key不同直接刪除節(jié)點(diǎn)
deleteChild(returnFiber, child);
}
child = child.sibling;
}
// 新的Fiber節(jié)點(diǎn)
const created = createFiberFromElement(element, returnFiber.mode, lanes);
created.ref = coerceRef(returnFiber, currentFirstChild, element);
created.return = returnFiber;
return created;
}
多節(jié)點(diǎn)Diff
源碼中將多節(jié)點(diǎn)分為了數(shù)組節(jié)點(diǎn)和可迭代節(jié)點(diǎn)。
if (isArray(newChild)) {
return reconcileChildrenArray(
returnFiber,
currentFirstChild,
newChild,
lanes,
);
}
if (getIteratorFn(newChild)) {
return reconcileChildrenIterator(
returnFiber,
currentFirstChild,
newChild,
lanes,
);
}
對(duì)應(yīng)的Diff函數(shù)分別是reconcileChildrenArray和reconcileChildrenIterator。它們的核心Diff邏輯是相同的，所以只分析數(shù)組節(jié)點(diǎn)的Diff —— reconcileChildrenArray函數(shù)。
這一段的代碼比較長，但邏輯很清晰，從分割線分為兩輪遍歷。
- 第一輪遍歷的是順序相同且key也相同的節(jié)點(diǎn)，這些節(jié)點(diǎn)需要做更新操作。
- 第二輪遍歷的是順序不同，可能key也不同的節(jié)點(diǎn)，這些節(jié)點(diǎn)需要做新增、移動(dòng)或刪除操作。
第一輪遍歷只針對(duì)key和順序都相同的情況，這些key對(duì)應(yīng)的節(jié)點(diǎn)位置沒有發(fā)生改變，只需要做更新操作，一旦遍歷遇到key不同的情況就需要跳出循環(huán)。
// 舊節(jié)點(diǎn) <li key="0"/> <li key="1"/> <li key="2"/> // 新節(jié)點(diǎn) <li key="0"/> <li key="1"/> <li key="5"/> // key="5"不同，跳出遍歷 // 第一輪遍歷的節(jié)點(diǎn) <li key="0"/> <li key="1"/> // <li key="2"/>和<li key="5"/>留在第二輪遍歷比較。
在第一輪遍歷完后也分為兩種情況。
- 新節(jié)點(diǎn)數(shù)量少于舊節(jié)點(diǎn)數(shù)量，這時(shí)候需要把多余的舊節(jié)點(diǎn)標(biāo)記為刪除。
- 新節(jié)點(diǎn)數(shù)量大于舊節(jié)點(diǎn)數(shù)量，這時(shí)候需要把多余的新節(jié)點(diǎn)標(biāo)記為新增。
第二輪遍歷針對(duì)key不同或順序不同的情況，可能情況如下：
// 舊節(jié)點(diǎn) <li key="0"/> <li key="1"/> <li key="2"/> // 新節(jié)點(diǎn) <li key="0"/> <li key="2"/> <li key="1"/> // 第二輪遍歷對(duì)比<li key="2"/>、<li key="1"/>這兩個(gè)節(jié)點(diǎn)
第二輪的遍歷會(huì)稍微復(fù)雜一點(diǎn)，后文在細(xì)講。
詳細(xì)的代碼如下。
reconcileChildrenArray
function reconcileChildrenArray(
returnFiber: Fiber,
currentFirstChild: Fiber | null,
newChildren: Array<*>,
lanes: Lanes,
): Fiber | null {
// 函數(shù)返回的Fiber節(jié)點(diǎn)
let resultingFirstChild: Fiber | null = null;
let previousNewFiber: Fiber | null = null;
// oldFiber為鏈表
let oldFiber = currentFirstChild;
// 用來判斷節(jié)點(diǎn)是否移動(dòng)
let lastPlacedIndex = 0;
let newIdx = 0;
let nextOldFiber = null;
// 第一輪遍歷，只遍歷key相同的節(jié)點(diǎn)
for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
if (oldFiber.index > newIdx) {
nextOldFiber = oldFiber;
oldFiber = null;
} else {
// 每次循環(huán)舊的fiber節(jié)點(diǎn)都會(huì)指向兄弟元素也就是下次循環(huán)的fiber節(jié)點(diǎn)
nextOldFiber = oldFiber.sibling;
}
// key相同返回fiber節(jié)點(diǎn)，key不同返回null
// 如果type相同復(fù)用節(jié)點(diǎn)，不同返回新節(jié)點(diǎn)
const newFiber = updateSlot(
returnFiber,
oldFiber,
newChildren[newIdx],
lanes,
);
// newFiber為null表示key不同，跳出循環(huán)
if (newFiber === null) {
if (oldFiber === null) {
oldFiber = nextOldFiber;
}
break;
}
// newFiber.alternate為null就是新節(jié)點(diǎn)，說明type不同創(chuàng)建了新fiber節(jié)點(diǎn)
if (oldFiber && newFiber.alternate === null) {
// 需要把oldFiber標(biāo)記刪除
deleteChild(returnFiber, oldFiber);
}
// 放置節(jié)點(diǎn),更新lastPlacedIndex
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
// 組成新fiber節(jié)點(diǎn)鏈
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
oldFiber = nextOldFiber;
}
/*
第一輪遍歷完后新節(jié)點(diǎn)數(shù)量少于舊節(jié)點(diǎn)數(shù)量
newChildren已經(jīng)遍歷完，刪除掉剩下的fiber節(jié)點(diǎn)，可能情況如下 ⬇️
以前
<li key="0"/>
<li key="1"/>
<li key="2"/>
新的
<li key="0"/>
<li key="1"/>
就會(huì)把<li key="2"/>刪除
*/
if (newIdx === newChildren.length) {
deleteRemainingChildren(returnFiber, oldFiber);
return resultingFirstChild;
}
/*
第一輪遍歷完新節(jié)點(diǎn)數(shù)量大于舊節(jié)點(diǎn)數(shù)量
oldFiber已經(jīng)遍歷完，可能情況如下 ⬇️
以前
<li key="0"/>
<li key="1"/>
新的
<li key="0"/>
<li key="1"/>
<li key="2"/>
就會(huì)添加新的<li key="2"/>，這一段是新節(jié)點(diǎn)的插入邏輯
*/
if (oldFiber === null) {
for (; newIdx < newChildren.length; newIdx++) {
const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
if (newFiber === null) {
continue;
}
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
// 組成新fiber節(jié)點(diǎn)鏈
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
}
return resultingFirstChild;
}
// ---------------------------------------------------------------------
// 用剩余的oldFiber創(chuàng)建一個(gè)key->fiber節(jié)點(diǎn)的Map，方便用key來獲取對(duì)應(yīng)的舊fiber節(jié)點(diǎn)
const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
// 第二輪遍歷，繼續(xù)遍歷剩余的節(jié)點(diǎn)，這些節(jié)點(diǎn)可能是需要移動(dòng)或者刪除的
for (; newIdx < newChildren.length; newIdx++) {
// 從map中獲取對(duì)應(yīng)對(duì)應(yīng)key的舊節(jié)點(diǎn)，返回更新后的新節(jié)點(diǎn)
const newFiber = updateFromMap(
existingChildren,
returnFiber,
newIdx,
newChildren[newIdx],
lanes,
);
if (newFiber !== null) {
// 復(fù)用的新節(jié)點(diǎn)，從map里刪除老的節(jié)點(diǎn)，對(duì)應(yīng)的情況可能是位置的改變
if (newFiber.alternate !== null) {
// 復(fù)用的節(jié)點(diǎn)要移除map，因?yàn)閙ap里剩余的節(jié)點(diǎn)都會(huì)被標(biāo)記Deletion刪除
existingChildren.delete(
newFiber.key === null ? newIdx : newFiber.key,
);
}
// 放置節(jié)點(diǎn)同時(shí)節(jié)點(diǎn)判斷是否移動(dòng)
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
}
}
// 刪除剩下的無用節(jié)點(diǎn)
existingChildren.forEach(child => deleteChild(returnFiber, child));
return resultingFirstChild;
}
第一輪遍歷比較好理解，這里再細(xì)分析一下第二輪遍歷，因?yàn)榈诙啎?huì)出現(xiàn)復(fù)用是否需要移動(dòng)的問題。
第二輪遍歷首先遍歷剩余的oldFiber，組成一個(gè)key -> 舊fiber節(jié)點(diǎn)的Map，這用可以通過key來快速的獲取舊節(jié)點(diǎn)。
接下來的遍歷依然是使用的新節(jié)點(diǎn)為遍歷對(duì)象，每次遍歷使用新節(jié)點(diǎn)的key從Map中取出舊節(jié)點(diǎn)來對(duì)比是否能復(fù)用，對(duì)應(yīng)的函數(shù)為updateFromMap。
如果節(jié)點(diǎn)存在alternate屬性，則是復(fù)用的節(jié)點(diǎn)，這時(shí)候需要將它從existingChildren里移除，后續(xù)會(huì)把第二輪遍歷完后依然存在在existingChildren里的節(jié)點(diǎn)標(biāo)記為刪除。
如何判斷節(jié)點(diǎn)移動(dòng)了？
這里存在一個(gè)變量lastPlacedIndex用來判斷節(jié)點(diǎn)是否移動(dòng)，每次將節(jié)點(diǎn)添加到新的Fiber鏈表中，都會(huì)更新這個(gè)值。
當(dāng)復(fù)用的節(jié)點(diǎn)oldIndex小于lastPlacedIndex時(shí)，則為移動(dòng)，如果不需要移動(dòng)，則會(huì)將lastPlacedIndex更新為較大的oldIndex，下一個(gè)節(jié)點(diǎn)會(huì)以新值判斷，代碼如下：
function placeChild(
newFiber: Fiber,
lastPlacedIndex: number,
newIndex: number,
): number {
newFiber.index = newIndex;
const current = newFiber.alternate;
if (current !== null) {
const oldIndex = current.index;
if (oldIndex < lastPlacedIndex) {
// 節(jié)點(diǎn)移動(dòng)
newFiber.flags = Placement;
return lastPlacedIndex;
} else {
// 節(jié)點(diǎn)位置無變化
return oldIndex;
}
} else {
// 插入的新節(jié)點(diǎn)
newFiber.flags = Placement;
return lastPlacedIndex;
}
}
舉個(gè)例子：
// 舊 abcd // 新 acbd
abcd均為key值。
第一輪遍歷后剩下的需要對(duì)比節(jié)點(diǎn):
// 舊 bcd // 新 cbd
a節(jié)點(diǎn)在第一輪已經(jīng)復(fù)用，并且調(diào)用過placeChild，這時(shí)lastPlacedIndex值為0。
進(jìn)入第二輪遍歷，依然是以新節(jié)點(diǎn)為遍歷對(duì)象。
c => 在舊節(jié)點(diǎn)中存在，可復(fù)用，它的index在舊節(jié)點(diǎn)中為2，2 > lastPlacedIndex(0)，不需要移動(dòng),將lastPlacedIndex賦值為2。 b => 在舊節(jié)點(diǎn)中存在，可復(fù)用，它的index在舊節(jié)點(diǎn)中為1，1 < lastPlacedIndex(2)，需要移動(dòng)，標(biāo)記Placement。 d => 在舊節(jié)點(diǎn)中存在，可復(fù)用，它的index在舊節(jié)點(diǎn)中為3，3 > lastPlacedIndex(2)，不需要移動(dòng)。
由這個(gè)例子可以看出，React中將右側(cè)不需要移動(dòng)的節(jié)點(diǎn)作為參照，將需要移動(dòng)的節(jié)點(diǎn)都是統(tǒng)一從左向右移動(dòng)的。
在后續(xù)Layout階段會(huì)將這里標(biāo)記了Placement的節(jié)點(diǎn)做insertBefore操作。
總結(jié)
React中的Diff算法核心代碼不算很長，但是卻引入key巧妙的將復(fù)雜度由O(n3 )變?yōu)榱薕(n)。
碼農(nóng)內(nèi)卷太嚴(yán)重，所以不得不學(xué)習(xí)源碼了。
以上就是react diff算法源碼解析的詳細(xì)內(nèi)容，更多關(guān)于react diff算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
修復(fù)Next.js中window?is?not?defined方法詳解
這篇文章主要為大家介紹了修復(fù)Next.js中window?is?not?defined方法詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-12-12
React不能將useMemo設(shè)置為默認(rèn)方法原因詳解
這篇文章主要為大家介紹了React不能將useMemo設(shè)置為默認(rèn)方法原因詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪<BR>2022-07-07
這篇文章主要介紹了如何在React中直接使用Redux,目前redux在react中使用是最多的，所以我們需要將之前編寫的redux代碼，融入到react當(dāng)中去，本文給大家詳細(xì)講解，需要的朋友可以參考下2022-12-12
從零開始學(xué)習(xí)搭建React腳手架項(xiàng)目
這篇文章主要介紹了從零開始學(xué)習(xí)搭建React腳手架項(xiàng)目，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-08-08
React Fiber結(jié)構(gòu)的創(chuàng)建步驟
這篇文章主要介紹了React Fiber結(jié)構(gòu)的創(chuàng)建步驟，幫助大家更好的理解和學(xué)習(xí)使用React，感興趣的朋友可以了解下2021-04-04
這篇文章主要為大家詳細(xì)介紹了的React?Refs屬性，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
React如何使用axios請(qǐng)求數(shù)據(jù)并把數(shù)據(jù)渲染到組件
這篇文章主要介紹了React如何使用axios請(qǐng)求數(shù)據(jù)并把數(shù)據(jù)渲染到組件，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-08-08
每天一個(gè)hooks學(xué)習(xí)之useUpdateEffect
這篇文章主要為大家介紹了每天一個(gè)hooks學(xué)習(xí)之useUpdateEffect使用示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-05-05
這篇文章主要介紹了react中使用css的7中方式(最全總結(jié))，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2019-02-02
React前端開發(fā)createElement源碼解讀
這篇文章主要為大家介紹了React前端開發(fā)createElement源碼解讀，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-11-11