React diff算法超詳細講解
上一章中 react 的 render 階段，其中 begin 時會調用 reconcileChildren函數， reconcileChildren 中做的事情就是 react 知名的 diff 過程，本章會對 diff 算法進行講解。
diff 算法介紹
react 的每次更新，都會將新的 ReactElement 內容與舊的 fiber 樹作對比，比較出它們的差異後，構建新的 fiber 樹，將差異點放入更新隊列之中，從而對真實 dom 進行 render。簡單來說就是如何通過最小代價將舊的 fiber 樹轉換為新的 fiber 樹。
經典的 diff 算法 中，將一棵樹轉為另一棵樹的最低時間復雜度為 O(n^3)，其中 n 為樹種節點的個數。假如采用這種 diff 算法，一個應用有 1000 個節點的情況下，需要比較 十億 次才能將 dom 樹更新完成，顯然這個性能是無法讓人接受的。
因此，想要將 diff 應用於 virtual dom 中，必須實現一種高效的 diff 算法。React 便通過制定瞭一套大膽的策略，實現瞭 O(n) 的時間復雜度更新 virtual dom。
diff 策略
react 將 diff 算法優化到 O(n) 的時間復雜度，基於瞭以下三個前提策略：
- 隻對同級元素進行比較。Web UI 中 DOM 節點跨層級的移動操作特別少，可以忽略不計，如果出現跨層級的 dom 節點更新，則不進行復用。
- 兩個不同類型的組件會產生兩棵不同的樹形結構。
- 對同一層級的子節點，開發者可以通過
key來確定哪些子元素可以在不同渲染中保持穩定。
上面的三種 diff 策略，分別對應著 tree diff、component diff 和 element diff。
tree diff
根據策略一，react 會對 fiber 樹進行分層比較，隻比較同級元素。這裡的同級指的是同一個父節點下的子節點(往上的祖先節點也都是同一個)，而不是樹的深度相同。
如上圖所示，react 的 tree diff 是采用深度優先遍歷，所以要比較的元素向上的祖先元素都會一致，即圖中會對相同顏色的方框內圈出的元素進行比較，例如左邊樹的 A 節點下的子節點 C、D 會與右邊樹 A 節點下的 C、D、E進行比較。
當元素出現跨層級的移動時，例如下圖：
A 子樹從 root 節點下到瞭 B 節點下，在 react diff 過程中並不會直接將 A 子樹移動到 B 子樹下，而是進行如下操作：
- 在 root 節點下刪除 A 節點
- 在 B 節點下創建 A 子節點
- 在新創建的 A 子節點下創建 C、D 節點
component diff
對於組件之間的比較，隻要它們的類型不同，就判斷為它們是兩棵不同的樹形結構，直接會將它們給替換掉。
例如下面的兩棵樹，左邊樹 B 節點和右邊樹 K 節點除瞭類型不同(比如 B 為 div 類型，K 為 p 類型)，內容完全一致，但 react 依然後直接替換掉整個節點。實際經過的變換是：
- 在 root 節點下創建 K 節點
- 在 K 節點下創建 E、F 節點
- 在 F 節點下創建 G、H 節點
- 在 root 節點下刪除 B 子節點
雖然如果在本例中改變類型復用子元素性能會更高一點，但是在時機應用開發中類型不一致子內容完全一致的情況極少，對這種情況過多判斷反而會增加時機復雜度，降低平均性能。
element diff
react 對於同層級的元素進行比較時，會通過 key 對元素進行比較以識別哪些元素可以穩定的渲染。同級元素的比較存在插入、刪除和移動三種操作。
如下圖左邊的樹想要轉變為右邊的樹：
實際經過的變換如下：
- 將 root 節點下 A 子節點移動至 B 子節點之後
- 在 root 節點下新增 E 子節點
- 將 root 節點下 C 子節點刪除
結合源碼看 diff
整體流程
diff 算法從 reconcileChildren 函數開始，根據當前 fiber 是否存在，決定是直接渲染新的 ReactElement 內容還是與當前 fiber 去進行 Diff，相關參考視頻講解：傳送門
export function reconcileChildren(
current: Fiber | null, // 當前 fiber 節點
workInProgress: Fiber, // 父 fiber
nextChildren: any, // 新生成的 ReactElement 內容
renderLanes: Lanes, // 渲染的優先級
) {
if (current === null) {
// 如果當前 fiber 節點為空，則直接將新的 ReactElement 內容生成新的 fiber
workInProgress.child = mountChildFibers(
workInProgress,
null,
nextChildren,
renderLanes,
);
} else {
// 當前 fiber 節點不為空，則與新生成的 ReactElement 內容進行 diff
workInProgress.child = reconcileChildFibers(
workInProgress,
current.child,
nextChildren,
renderLanes,
);
}
}
因為我們主要是要學習 diff 算法，所以我們暫時先不關心 mountChildFibers 函數，主要關註 reconcileChildFibers ，我們來看一下它的源碼：
function reconcileChildFibers(
returnFiber: Fiber, // 父 Fiber
currentFirstChild: Fiber | null, // 父 fiber 下要對比的第一個子 fiber
newChild: any, // 更新後的 React.Element 內容
lanes: Lanes, // 更新的優先級
): Fiber | null {
// 對新創建的 ReactElement 最外層是 fragment 類型單獨處理，比較其 children
const isUnkeyedTopLevelFragment =
typeof newChild === 'object' &&
newChild !== null &&
newChild.type === REACT_FRAGMENT_TYPE &&
newChild.key === null;
if (isUnkeyedTopLevelFragment) {
newChild = newChild.props.children;
}
// 對更新後的 React.Element 是單節點的處理
if (typeof newChild === 'object' && newChild !== null) {
switch (newChild.$$typeof) {
// 常規 react 元素
case REACT_ELEMENT_TYPE:
return placeSingleChild(
reconcileSingleElement(
returnFiber,
currentFirstChild,
newChild,
lanes,
),
);
// react.portal 類型
case REACT_PORTAL_TYPE:
return placeSingleChild(
reconcileSinglePortal(
returnFiber,
currentFirstChild,
newChild,
lanes,
),
);
// react.lazy 類型
case REACT_LAZY_TYPE:
if (enableLazyElements) {
const payload = newChild._payload;
const init = newChild._init;
return reconcileChildFibers(
returnFiber,
currentFirstChild,
init(payload),
lanes,
);
}
}
// 更新後的 React.Element 是多節點的處理
if (isArray(newChild)) {
return reconcileChildrenArray(
returnFiber,
currentFirstChild,
newChild,
lanes,
);
}
// 迭代器函數的單獨處理
if (getIteratorFn(newChild)) {
return reconcileChildrenIterator(
returnFiber,
currentFirstChild,
newChild,
lanes,
);
}
throwOnInvalidObjectType(returnFiber, newChild);
}
// 純文本節點的類型處理
if (typeof newChild === 'string' || typeof newChild === 'number') {
return placeSingleChild(
reconcileSingleTextNode(
returnFiber,
currentFirstChild,
'' + newChild,
lanes,
),
);
}
if (__DEV__) {
if (typeof newChild === 'function') {
warnOnFunctionType(returnFiber);
}
}
// 不符合以上情況都視為 empty，直接從父節點刪除所有舊的子 Fiber
return deleteRemainingChildren(returnFiber, currentFirstChild);
}
入口函數中，接收 returnFiber、currentFirstChild、newChild、lanes 四個參數，其中，根據 newChid 的類型，我們主要關註幾個比較常見的類型的 diff，單 React 元素的 diff、純文本類型的 diff 和 數組類型的 diff。
所以根據 ReactElement 類型走的不同流程如下：
新內容為 REACT_ELEMENT_TYPE
當新創建的節點 type 為 object 時，我們看一下其為 REACT_ELEMENT_TYPE 類型的 diff，即 placeSingleChild(reconcileSingleElement(...)) 函數。
先看一下 reconcileSingleElement 函數的源碼：
function reconcileSingleElement(
returnFiber: Fiber, // 父 fiber
currentFirstChild: Fiber | null, // 父 fiber 下第一個開始對比的舊的子 fiber
element: ReactElement, // 當前的 ReactElement內容
lanes: Lanes, // 更新的優先級
): Fiber {
const key = element.key;
let child = currentFirstChild;
// 處理舊的 fiber 由多個節點變成新的 fiber 一個節點的情況
// 循環遍歷父 fiber 下的舊的子 fiber，直至遍歷完或者找到 key 和 type 都與新節點相同的情況
while (child !== null) {
if (child.key === key) {
const elementType = element.type;
if (elementType === REACT_FRAGMENT_TYPE) {
if (child.tag === Fragment) {
// 如果新的 ReactElement 和舊 Fiber 都是 fragment 類型且 key 相等
// 對舊 fiber 後面的所有兄弟節點添加 Deletion 副作用標記，用於 dom 更新時刪除
deleteRemainingChildren(returnFiber, child.sibling);
// 通過 useFiber, 基於舊的 fiber 和新的 props.children，克隆生成一個新的 fiber，新 fiber 的 index 為 0，sibling 為 null
// 這便是所謂的 fiber 復用
const existing = useFiber(child, element.props.children);
existing.return = returnFiber;
if (__DEV__) {
existing._debugSource = element._source;
existing._debugOwner = element._owner;
}
return existing;
}
} else {
if (
// 如果新的 ReactElement 和舊 Fiber 的 key 和 type 都相等
child.elementType === elementType ||
(__DEV__
? isCompatibleFamilyForHotReloading(child, element)
: false) ||
(enableLazyElements &&
typeof elementType === 'object' &&
elementType !== null &&
elementType.$$typeof === REACT_LAZY_TYPE &&
resolveLazy(elementType) === child.type)
) {
// 對舊 fiber 後面的所有兄弟節點添加 Deletion 副作用標記，用於 dom 更新時刪除
deleteRemainingChildren(returnFiber, child.sibling);
// 通過 useFiber 復用新節點並返回
const existing = useFiber(child, element.props);
existing.ref = coerceRef(returnFiber, child, element);
existing.return = returnFiber;
if (__DEV__) {
existing._debugSource = element._source;
existing._debugOwner = element._owner;
}
return existing;
}
}
// 若 key 相同但是 type 不同說明不匹配，移除舊 fiber 及其後面的兄弟 fiber
deleteRemainingChildren(returnFiber, child);
break;
} else {
// 若 key 不同，對當前的舊 fiber 添加 Deletion 副作用標記，繼續對其兄弟節點遍歷
deleteChild(returnFiber, child);
}
child = child.sibling;
}
// 都遍歷完之後說明沒有匹配到 key 和 type 都相同的 fiber
if (element.type === REACT_FRAGMENT_TYPE) {
// 如果新節點是 fragment 類型，createFiberFromFragment 創建新的 fragment 類型 fiber並返回
const created = createFiberFromFragment(
element.props.children,
returnFiber.mode,
lanes,
element.key,
);
created.return = returnFiber;
return created;
} else {
// createFiberFromElement 創建 fiber 並返回
const created = createFiberFromElement(element, returnFiber.mode, lanes);
created.ref = coerceRef(returnFiber, currentFirstChild, element);
created.return = returnFiber;
return created;
}
}
根據源碼我們可以得知，reconcileSingleElement 函數中，會遍歷父 fiber 下所有的舊的子 fiber，尋找與新生成的 ReactElement 內容的 key 和 type 都相同的子 fiber。每次遍歷對比的過程中：
- 若當前舊的子 fiber 與新內容 key 或 type 不一致，對當前舊的子 fiber 添加
Deletion副作用標記（用於 dom 更新時刪除），繼續對比下一個舊子 fiber - 若當前舊的子 fiber 與新內容 key 或 type 一致，則判斷為可復用，通過
deleteRemainingChildren對該子 fiber 後面所有的兄弟 fiber 添加Deletion副作用標記，然後通過useFiber基於該子 fiber 和新內容的 props 生成新的 fiber 進行復用，結束遍歷。
若都遍歷完沒找到與新內容 key 或 type 子 fiber，此時父 fiber 下的所有舊的子 fiber 都已經添加瞭 Deletion 副作用標記，通過 createFiberFromElement 基於新內容創建新的 fiber 並將其 return指向父 fiber。
再來看 placeSingleChild 的源碼：
function placeSingleChild(newFiber: Fiber): Fiber {
if (shouldTrackSideEffects && newFiber.alternate === null) {
newFiber.flags |= Placement;
}
return newFiber;
}
placeSingleChild 中做的事情更為簡單，就是將 reconcileSingleElement 中生成的新 fiber 打上 Placement 的標記，表示 dom 更新渲染時要進行插入。
新內容為純文本類型
當新創建節點的 typeof 為 string 或者 number 時，表示是純文本節點，使用 placeSingleChild(reconcileSingleTextNode(...)) 函數進行 diff。
placeSingleChild 前面說過瞭，我們主要看 reconcileSingleTextNode 的源碼：
function reconcileSingleTextNode(
returnFiber: Fiber, currentFirstChild: Fiber | null, textContent: string, lanes: Lanes,
): Fiber {
if (currentFirstChild !== null && currentFirstChild.tag === HostText) {
// deleteRemainingChildren 對舊 fiber 後面的所有兄弟節點添加 Deletion 副作用標記，用於 dom 更新時刪除
// useFiber 傳入 textContext 復用當前 fiber
deleteRemainingChildren(returnFiber, currentFirstChild.sibling);
const existing = useFiber(currentFirstChild, textContent);
existing.return = returnFiber;
return existing;
}
// 若未匹配到，createFiberFromText 創建新的 fiber
deleteRemainingChildren(returnFiber, currentFirstChild);
const created = createFiberFromText(textContent, returnFiber.mode, lanes);
created.return = returnFiber;
return created;
}
新內容為純文本時 diff 比較簡單，隻需要判斷當前父 fiber 的第一個舊子 fiber 類型：
- 當前 fiber 也為文本類型的節點時，
deleteRemainingChildren對第一個舊子 fiber 的所有兄弟 fiber 添加Deletion副作用標記，然後通過useFiber基於當前 fiber 和 textContent 創建新的 fiber 復用，將其 return 指向父 fiber - 否則通過
deleteRemainingChildren對所有舊的子 fiber 添加Deletion副作用標記，然後createFiberFromText創建新的文本類型 fiber 節點，將其 return 指向父 fiber
所以對文本類型 diff 的流程如下：
新內容為數組類型
上面所說的兩種情況，都是一個或多個子 fiebr 變成單個 fiber。新內容為數組類型時，意味著要將一個或多個子 fiber 替換為多個 fiber，內容相對復雜，我們看一下 reconcileChildrenArray 的源碼：
function reconcileChildrenArray(
returnFiber: Fiber, currentFirstChild: Fiber | null, newChildren: Array<*>, lanes: Lanes,
): Fiber | null {
// 開發環境下會校驗 key 是否存在且合法，否則會報 warning
if (__DEV__) {
let knownKeys = null;
for (let i = 0; i < newChildren.length; i++) {
const child = newChildren[i];
knownKeys = warnOnInvalidKey(child, knownKeys, returnFiber);
}
}
let resultingFirstChild: Fiber | null = null; // 最終要返回的第一個子 fiber
let previousNewFiber: Fiber | null = null;
let oldFiber = currentFirstChild;
let lastPlacedIndex = 0;
let newIdx = 0;
let nextOldFiber = null;
// 因為在實際的應用開發中，react 發現更新的情況遠大於新增和刪除的情況，所以這裡優先處理更新
// 根據 oldFiber 的 index 和 newChildren 的下標，找到要對比更新的 oldFiber
for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
if (oldFiber.index > newIdx) {
nextOldFiber = oldFiber;
oldFiber = null;
} else {
nextOldFiber = oldFiber.sibling;
}
// 通過 updateSlot 來 diff oldFiber 和新的 child，生成新的 Fiber
// updateSlot 與上面兩種類型的 diff 類似，如果 oldFiber 可復用，則根據 oldFiber 和 child 的 props 生成新的 fiber；否則返回 null
const newFiber = updateSlot(
returnFiber,
oldFiber,
newChildren[newIdx],
lanes,
);
// newFiber 為 null 說明不可復用，退出第一輪的循環
if (newFiber === null) {
if (oldFiber === null) {
oldFiber = nextOldFiber;
}
break;
}
if (shouldTrackSideEffects) {
if (oldFiber && newFiber.alternate === null) {
deleteChild(returnFiber, oldFiber);
}
}
// 記錄復用的 oldFiber 的 index，同時給新 fiber 打上 Placement 副作用標簽
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
if (previousNewFiber === null) {
// 如果上一個 newFiber 為 null，說明這是第一個生成的 newFiber，設置為 resultingFirstChild
resultingFirstChild = newFiber;
} else {
// 否則構建鏈式關系
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
oldFiber = nextOldFiber;
}
if (newIdx === newChildren.length) {
// newChildren遍歷完瞭，說明剩下的 oldFiber 都是待刪除的 Fiber
// 對剩下 oldFiber 標記 Deletion
deleteRemainingChildren(returnFiber, oldFiber);
return resultingFirstChild;
}
if (oldFiber === null) {
// olderFiber 遍歷完瞭
// newChildren 剩下的節點都是需要新增的節點
for (; newIdx < newChildren.length; newIdx++) {
// 遍歷剩下的 child，通過 createChild 創建新的 fiber
const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
if (newFiber === null) {
continue;
}
// 處理dom移動，// 記錄 index，同時給新 fiber 打上 Placement 副作用標簽
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
// 將新創建 fiber 加入到 fiber 鏈表樹中
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
}
return resultingFirstChild;
}
// oldFiber 和 newChildren 都未遍歷完
// mapRemainingChildren 生成一個以 oldFiber 的 key 為 key， oldFiber 為 value 的 map
const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
// 對剩下的 newChildren 進行遍歷
for (; newIdx < newChildren.length; newIdx++) {
// 找到 mapRemainingChildren 中 key 相等的 fiber, 創建新 fiber 復用
const newFiber = updateFromMap(
existingChildren,
returnFiber,
newIdx,
newChildren[newIdx],
lanes,
);
if (newFiber !== null) {
if (shouldTrackSideEffects) {
if (newFiber.alternate !== null) {
// 刪除當前找到的 fiber
existingChildren.delete(
newFiber.key === null ? newIdx : newFiber.key,
);
}
}
// 處理dom移動，記錄 index，同時給新 fiber 打上 Placement 副作用標簽
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
// 將新創建 fiber 加入到 fiber 鏈表樹中
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
}
}
if (shouldTrackSideEffects) {
// 剩餘的舊 fiber 的打上 Deletion 副作用標簽
existingChildren.forEach(child => deleteChild(returnFiber, child));
}
return resultingFirstChild;
}
從上述代碼我們可以得知，對於新增內容為數組時，react 會對舊 fiber 和 newChildren 進行遍歷。
首先先對 newChildren 進行第一輪遍歷，將當前的 oldFiber 與 當前 newIdx 下標的 newChild 通過 updateSlot 進行 diff，diff 的流程和上面單節點的 diff 類似，然後返回 diff 後的結果：
- 如果 diff 後 oldFiber 和 newIdx 的 key 和 type 一致，說明可復用。根據 oldFiber 和 newChild 的 props 生成新的 fiber，通過
placeChild給新生成的 fiber 打上Placement副作用標記，同時新 fiber 與之前遍歷生成的新 fiber 構建鏈表樹關系。然後繼續執行遍歷，對下一個 oldFiber 和下一個 newIdx 下標的 newFiber 繼續 diff - 如果 diff 後 oldFiber 和 newIdx 的 key 或 type 不一致，那麼說明不可復用，返回的結果為 null，第一輪遍歷結束
第一輪遍歷結束後，可能會執行以下幾種情況：
- 若 newChildren 遍歷完瞭，那剩下的 oldFiber 都是待刪除的，通過
deleteRemainingChildren對剩下的 oldFiber 打上Deletion副作用標記 - 若 oldFiber 遍歷完瞭，那剩下的 newChildren 都是需要新增的，遍歷剩下的 newChildren，通過
createChild創建新的 fiber，placeChild給新生成的 fiber 打上Placement副作用標記並添加到 fiber 鏈表樹中。 - 若 oldFiber 和 newChildren 都未遍歷完，通過
mapRemainingChildren創建一個以剩下的 oldFiber 的 key 為 key，oldFiber 為 value 的 map。然後對剩下的 newChildren 進行遍歷，通過updateFromMap在 map 中尋找具有相同 key 創建新的fiber(若找到則基於 oldFiber 和 newChild 的 props創建，否則直接基於 newChild 創建)，則從 map 中刪除當前的 key，然後placeChild給新生成的 fiber 打上Placement副作用標記並添加到 fiber 鏈表樹中。遍歷完之後則 existingChildren 還剩下 oldFiber 的話，則都是待刪除的 fiber，deleteChild對其打上Deletion副作用標記。
diff 後的渲染
diff 流程結束後，會形成新的 fiber 鏈表樹，鏈表樹上的 fiber 通過 flags 字段做瞭副作用標記，主要有以下幾種：
- Deletion：會在渲染階段對對應的 dom 做刪除操作
- Update：在 fiber.updateQueue 上保存瞭要更新的屬性，在渲染階段會對 dom 做更新操作
- Placement：Placement 可能是插入也可能是移動，實際上兩種都是插入動作。react 在更新時會優先去尋找要插入的 fiber 的 sibling，如果找到瞭執行 dom 的
insertBefore方法，如果沒有找到就執行 dom 的appendChild方法，從而實現瞭新節點插入位置的準確性
在 completeUnitWork 階段結束後，react 會根據 fiber 鏈表樹的 flags，構建一個 effectList 鏈表，裡面記錄瞭哪些 fiber 需要進行插入、刪除、更新操作，在後面的 commit 階段進行真實 dom 節點的更新，下一章將詳細講述 commit 階段。
到此這篇關於React diff算法超詳細講解的文章就介紹到這瞭,更多相關React diff算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！