react源碼解析9.diff算法
視頻課程（高效學(xué)習(xí)）：進入課程
課程目錄：
6.legacy和concurrent模式入口函數(shù)
在render階段更新Fiber節(jié)點時，我們會調(diào)用reconcileChildFibers對比current Fiber和jsx對象構(gòu)建workInProgress Fiber莉御，這里current Fiber是指當前dom對應(yīng)的fiber樹且轨，jsx是class組件render方法或者函數(shù)組件的返回值。
在reconcileChildFibers中會根據(jù)newChild的類型來進入單節(jié)點的diff或者多節(jié)點diff
//ReactChildFiber.old.js
function reconcileChildFibers(
returnFiber: Fiber,
currentFirstChild: Fiber | null,
newChild: any,
): Fiber | null {
const isObject = typeof newChild === 'object' && newChild !== null;
if (isObject) {
switch (newChild.$$typeof) {
case REACT_ELEMENT_TYPE:
//單一節(jié)點diff
return placeSingleChild(
reconcileSingleElement(
returnFiber,
currentFirstChild,
newChild,
lanes,
),
);
}
}
//...
if (isArray(newChild)) {
//多節(jié)點diff
return reconcileChildrenArray(
returnFiber,
currentFirstChild,
newChild,
lanes,
);
}
// 刪除節(jié)點
return deleteRemainingChildren(returnFiber, currentFirstChild);
}
diff過程的主要流程如下圖：
我們知道對比兩顆樹的復(fù)雜度本身是O(n3)魄健，對我們的應(yīng)用來說這個是不能承受的量級赋铝，react為了降低復(fù)雜度，提出了三個前提：
只對同級比較沽瘦，跨層級的dom不會進行復(fù)用
不同類型節(jié)點生成的dom樹不同革骨，此時會直接銷毀老節(jié)點及子孫節(jié)點农尖，并新建節(jié)點
-
可以通過key來對元素diff的過程提供復(fù)用的線索，例如：
const a = ( <> <p key="0">0</p> <p key="1">1</p> </> ); const b = ( <> <p key="1">1</p> <p key="0">0</p> </> );
如果a和b里的元素都沒有key良哲，因為節(jié)點的更新前后文本節(jié)點不同盛卡，導(dǎo)致他們都不能復(fù)用，所以會銷毀之前的節(jié)點筑凫，并新建節(jié)點滑沧，但是現(xiàn)在有key了，b中的節(jié)點會在老的a中尋找key相同的節(jié)點嘗試復(fù)用巍实，最后發(fā)現(xiàn)只是交換位置就可以完成更新滓技，具體對比過程后面會講到。
單節(jié)點diff
單點diff有如下幾種情況：
- key和type相同表示可以復(fù)用節(jié)點
- key不同直接標記刪除節(jié)點蔫浆，然后新建節(jié)點
- key相同type不同殖属，標記刪除該節(jié)點和兄弟節(jié)點，然后新創(chuàng)建節(jié)點
function reconcileSingleElement(
returnFiber: Fiber,
currentFirstChild: Fiber | null,
element: ReactElement
): Fiber {
const key = element.key;
let child = currentFirstChild;
//child節(jié)點不為null執(zhí)行對比
while (child !== null) {
// 1.比較key
if (child.key === key) {
// 2.比較type
switch (child.tag) {
//...
default: {
if (child.elementType === element.type) {
// type相同則可以復(fù)用 返回復(fù)用的節(jié)點
return existing;
}
// type不同跳出
break;
}
}
//key相同瓦盛，type不同則把fiber及和兄弟fiber標記刪除
deleteRemainingChildren(returnFiber, child);
break;
} else {
//key不同直接標記刪除該節(jié)點
deleteChild(returnFiber, child);
}
child = child.sibling;
}
//新建新Fiber
}
多節(jié)點diff
多節(jié)點diff比較復(fù)雜洗显，我們分三種情況進行討論，其中a表示更新前的節(jié)點原环，b表示更新后的節(jié)點
-
屬性變化
const a = ( <> <p key="0" name='0'>0</p> <p key="1">1</p> </> ); const b = ( <> <p key="0" name='00'>0</p> <p key="1">1</p> </> );
-
type變化
const a = ( <> <p key="0">0</p> <p key="1">1</p> </> ); const b = ( <> <div key="0">0</div> <p key="1">1</p> </> );
-
新增節(jié)點
const a = ( <> <p key="0">0</p> <p key="1">1</p> </> ); const b = ( <> <p key="0">0</p> <p key="1">1</p> <p key="2">2</p> </> );
-
節(jié)點刪除
const a = ( <> <p key="0">0</p> <p key="1">1</p> <p key="2">2</p> </> ); const b = ( <> <p key="0">0</p> <p key="1">1</p> </> );
-
節(jié)點位置變化
const a = ( <> <p key="0">0</p> <p key="1">1</p> </> ); const b = ( <> <p key="1">1</p> <p key="0">0</p> </> );
在源碼中多節(jié)點diff有三個for循環(huán)遍歷（并不意味著所有更新都有經(jīng)歷三個遍歷挠唆，進入循環(huán)體有條件，也有條件跳出循環(huán)）嘱吗，第一個遍歷處理節(jié)點的更新（包括props更新和type更新和刪除）玄组，第二個遍歷處理其他的情況（節(jié)點新增），其原因在于在大多數(shù)的應(yīng)用中谒麦，節(jié)點更新的頻率更加頻繁俄讹，第三個處理位節(jié)點置改變
-
第一次遍歷
因為老的節(jié)點存在于current Fiber中，所以它是個鏈表結(jié)構(gòu)绕德，還記得Fiber雙緩存結(jié)構(gòu)嘛患膛，節(jié)點通過child、return耻蛇、sibling連接踪蹬，而newChildren存在于jsx當中，所以遍歷對比的時候臣咖，首先讓newChildren[i]與oldFiber對比跃捣，然后讓i++、nextOldFiber = oldFiber.sibling夺蛇。在第一輪遍歷中疚漆，會處理三種情況，其中第1，2兩種情況會結(jié)束第一次循環(huán)key不同娶聘，第一次循環(huán)結(jié)束
newChildren或者oldFiber遍歷完灵临，第一次循環(huán)結(jié)束
key同type不同，標記oldFiber為DELETION
-
key相同type相同則可以復(fù)用
newChildren遍歷完趴荸，oldFiber沒遍歷完，在第一次遍歷完成之后將oldFiber中沒遍歷完的節(jié)點標記為DELETION宦焦，即刪除的DELETION Tag
-
第二個遍歷
第二個遍歷考慮三種情況newChildren和oldFiber都遍歷完：多節(jié)點diff過程結(jié)束
newChildren沒遍歷完发钝，oldFiber遍歷完，將剩下的newChildren的節(jié)點標記為Placement波闹，即插入的Tag
newChildren和oldFiber沒遍歷完酝豪，則進入節(jié)點移動的邏輯
-
第三個遍歷
主要邏輯在placeChild函數(shù)中，例如更新前節(jié)點順序是ABCD精堕，更新后是ACDBnewChild中第一個位置的A和oldFiber第一個位置的A孵淘，key相同可復(fù)用，lastPlacedIndex=0
newChild中第二個位置的C和oldFiber第二個位置的B歹篓，key不同跳出第一次循環(huán)瘫证，將oldFiber中的BCD保存在map中
newChild中第二個位置的C在oldFiber中的index=2 > lastPlacedIndex=0不需要移動，lastPlacedIndex=2
newChild中第三個位置的D在oldFiber中的index=3 > lastPlacedIndex=2不需要移動庄撮，lastPlacedIndex=3
newChild中第四個位置的B在oldFiber中的index=1 < lastPlacedIndex=3,移動到最后
看圖更直觀
react源碼9.6例如更新前節(jié)點順序是ABCD背捌，更新后是DABC
newChild中第一個位置的D和oldFiber第一個位置的A，key不相同不可復(fù)用洞斯，將oldFiber中的ABCD保存在map中毡庆，lastPlacedIndex=0
-
newChild中第一個位置的D在oldFiber中的index=3 > lastPlacedIndex=0不需要移動，lastPlacedIndex=3
- newChild中第二個位置的A在oldFiber中的index=0 < lastPlacedIndex=3,移動到最后
- newChild中第三個位置的B在oldFiber中的index=1 < lastPlacedIndex=3,移動到最后
- newChild中第四個位置的C在oldFiber中的index=2 < lastPlacedIndex=3,移動到最后
看圖更直觀
react源碼9.7代碼如下：
//ReactChildFiber.old.js
function placeChild(newFiber, lastPlacedIndex, newIndex) {
newFiber.index = newIndex;
if (!shouldTrackSideEffects) {
return lastPlacedIndex;
}
var current = newFiber.alternate;
if (current !== null) {
var oldIndex = current.index;
if (oldIndex < lastPlacedIndex) {
//oldIndex小于lastPlacedIndex的位置 則將節(jié)點插入到最后
newFiber.flags = Placement;
return lastPlacedIndex;
} else {
return oldIndex;//不需要移動 lastPlacedIndex = oldIndex;
}
} else {
//新增插入
newFiber.flags = Placement;
return lastPlacedIndex;
}
}
//ReactChildFiber.old.js
function reconcileChildrenArray(
returnFiber: Fiber,//父fiber節(jié)點
currentFirstChild: Fiber | null,//childs中第一個節(jié)點
newChildren: Array<*>,//新節(jié)點數(shù)組 也就是jsx數(shù)組
lanes: Lanes,//lane相關(guān) 第12章介紹
): Fiber | null {
let resultingFirstChild: Fiber | null = null;//diff之后返回的第一個節(jié)點
let previousNewFiber: Fiber | null = null;//新節(jié)點中上次對比過的節(jié)點
let oldFiber = currentFirstChild;//正在對比的oldFiber
let lastPlacedIndex = 0;//上次可復(fù)用的節(jié)點位置 或者oldFiber的位置
let newIdx = 0;//新節(jié)點中對比到了的位置
let nextOldFiber = null;//正在對比的oldFiber
for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {//第一次遍歷
if (oldFiber.index > newIdx) {//nextOldFiber賦值
nextOldFiber = oldFiber;
oldFiber = null;
} else {
nextOldFiber = oldFiber.sibling;
}
const newFiber = updateSlot(//更新節(jié)點烙如，如果key不同則newFiber=null
returnFiber,
oldFiber,
newChildren[newIdx],
lanes,
);
if (newFiber === null) {
if (oldFiber === null) {
oldFiber = nextOldFiber;
}
break;//跳出第一次遍歷
}
if (shouldTrackSideEffects) {//檢查shouldTrackSideEffects
if (oldFiber && newFiber.alternate === null) {
deleteChild(returnFiber, oldFiber);
}
}
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);//標記節(jié)點插入
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
oldFiber = nextOldFiber;
}
if (newIdx === newChildren.length) {
deleteRemainingChildren(returnFiber, oldFiber);//將oldFiber中沒遍歷完的節(jié)點標記為DELETION
return resultingFirstChild;
}
if (oldFiber === null) {
for (; newIdx < newChildren.length; newIdx++) {//第2次遍歷
const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
if (newFiber === null) {
continue;
}
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);//插入新增節(jié)點
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
}
return resultingFirstChild;
}
// 將剩下的oldFiber加入map中
const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
for (; newIdx < newChildren.length; newIdx++) {//第三次循環(huán) 處理節(jié)點移動
const newFiber = updateFromMap(
existingChildren,
returnFiber,
newIdx,
newChildren[newIdx],
lanes,
);
if (newFiber !== null) {
if (shouldTrackSideEffects) {
if (newFiber.alternate !== null) {
existingChildren.delete(//刪除找到的節(jié)點
newFiber.key === null ? newIdx : newFiber.key,
);
}
}
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);//標記為插入的邏輯
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
}
}
if (shouldTrackSideEffects) {
//刪除existingChildren中剩下的節(jié)點
existingChildren.forEach(child => deleteChild(returnFiber, child));
}
return resultingFirstChild;
}
