Diff 的目的
react 是一個數(shù)據(jù)驅動的框架，通過將數(shù)據(jù)與 UI 關聯(lián)起來達到數(shù)據(jù)更新時同時更新 UI 更新的目的代承。對于 react web app 來說安岂，數(shù)據(jù)的變動最終會轉化為 dom 的變化褂始。當然 react 并不會對 dom 進行直接比較景埃，而是對比變化前的 fiber。對 fiber 的 diff 最終會反映到 dom 上粱哼。
先假設在 fiber 變化時不使用 diff 算法季二，即一旦 fiber 改變則刪除變化前的所有 fiber 并插入變化后的 fiber 。這種方法雖然簡便揭措，但存在性能問題胯舷，因為 dom 的刪除和創(chuàng)建都需要耗費時間。例如蜂筹，fiber 從 a, b, c 變?yōu)?a, c, b需纳。只需要將 b 插入到 c 之后即可芦倒，無需創(chuàng)建任何 fiber 艺挪。因此，需要一種方法來標記元素的變更兵扬，這就是 diff 算法麻裳。
如果變化后都存在多個元素，則屬于多節(jié)點的 diff器钟。多節(jié)點的 fiber diff 對于每一個 fiber 實際只存在兩種情況:
- Placement: 需要移動某個 fiber 的位置或插入一個新 fiber
- Deletion: 需要刪除某個 fiber
為什么移動或新增 dom 都屬于同一種情況津坑，因為 react 實際上最終會調用 Node.insertBefore() 來進行 placement 操作，其定義如下:
Node.insertBefore() 方法在參考節(jié)點之前插入一個擁有指定父節(jié)點的子節(jié)點傲霸。 如果給定的子節(jié)點是對文檔中現(xiàn)有節(jié)點的引用 疆瑰，insertBefore() 會將其從當前位置移動到新位置 （在將節(jié)點附加到其他節(jié)點之前眉反，不需要從其父節(jié)點刪除該節(jié)點）。
因此 react 并不關心該 fiber 是移動(已經(jīng)存在)還是新增(不存在需要創(chuàng)建)穆役。例如 fiber 從 a, b, c, d 變?yōu)?a, c, b,d寸五，那么 react 會將 b 這個 fiber 標記為 Placement。其余 fiber 不變耿币。在最終進行 dom 變化時調用 parent.insertBefore(d, b)梳杏。因此 diff 的目的并不是要嚴格的找出 fiber 從哪個位置移動到哪個位置，只需要得出哪些需要刪除淹接，哪些需要 Placement 即可十性。
算法
假設存在 now 以及 before 兩個 fiber 集合。為了簡化場景塑悼，認為 now 中的 fiber 在 before 中都存在劲适。這時候問題可以轉換為 如何移動 before 中的元素將其轉換為 now。react處理辦法為 右移 before 中的部分 fiber 將其轉換為 now厢蒜。例如减响，before 以及 after 中 key 的順序為:
before: a, b, c
now: a, c, b
那么標記 b 為 Placement 即可。對于這個任務郭怪，我們將 上一個位置不變的元素在 now 中的位置記為 lastKeepIndex支示，當遍歷 now 數(shù)組中的每個 fiber 時，如果該 fiber 在 before 數(shù)組中存在鄙才，且 颂鸿。則說明當前所遍歷到得 fiber 在:
- 變動前: 位于 lastKeepIndex 所標記的 fiber 的左邊。
- 變動后: 位于 lastKeepIndex 所標記的右邊攒庵，因為當前 fiber 為遍歷到的位置為最靠右邊的 fiber嘴纺。
這就意味這這個 fiber 是需要移動的。如果不滿足這個條件浓冒，則需要該 fiber 相對 lastKeepIndex 所標記的 fiber 位置沒有變動栽渴，無需改變。
當然稳懒，實際上不可能 now 中的 fiber 在 before 中都能找到闲擦。但這種同樣直接標記為 Placement 即可。同時在 before 中卻不在 now 中的需要元素標記為 Deletion场梆。為了方便這里我們定義 4 種類型的 Diff:
type Key = string | number
interface FiberNode {
'key': Key
}
// Move 與 Insert 實際上都為 Placement墅冷，這里為了方便說明將其分為兩種
type Diff = 'Move'|'Insert'|'Deletion'|'None'
整個 diff 的邏輯為:
function diff(before: FiberNode[], now: FiberNode[]): [Key, Diff][]{
// 將 fiber 轉換為 [key, index] 方式供后續(xù)使用
const beforeMap = new Map<Key, number>(before.map((n, i) => [n.key, i]));
let lastKeepIndex = -1;
const addOrmove = now.map(n => {
const beforeIndex = beforeMap.get(n.key)
let mutation: Diff = null;
// 如果這個 fiber 在 before 中不存在，則直接標記為 Insert
if(beforeIndex === undefined){
mutation = 'Insert'
}else{
// 刪除可以復用的 fiber或油，遍歷完成后剩下的則為需要標記刪除的 fiber
beforeMap.delete(n.key);
// 滿足條件寞忿，表明該 fiber 需要移動
if(beforeIndex < lastKeepIndex){
mutation = 'Move';
}else{
// 否則不需要移動，該 beforeIndex 作為新的 lastKeepIndex
lastKeepIndex = beforeIndex;
mutation = 'None'
}
}
return [n.key, mutation] as [Key, Diff]
})
// 標記需要刪除的 fiber
const deletion = Array.from(beforeMap.entries()).map(n => [n[0], 'Deletion'] as [Key, Diff])
return [...addOrmove, ...deletion]
}
const before: FiberNode[] = [
{key: 'a'},
{key: 'b'},
{key: 'c'},
{key: 'd'},
{key: 'x'},
]
const after: FiberNode[] = [
{key: 'f'},
{key: 'c'},
{key: 'b'},
{key: 'e'},
{key: 'a'},
{key: 'd'}
]
console.info(diff(before, after))
[ [ 'f', 'Insert' ],
[ 'c', 'None' ],
[ 'b', 'Move' ],
[ 'e', 'Insert' ],
[ 'a', 'Move' ],
[ 'd', 'None' ],
[ 'x', 'Deletion' ] ]
如何應用到真實 dom
在得到 diff 的結果后顶岸，react 通過兩個 dom 操作函數(shù)來將 diff 應用到真實的 dom:
- Node.insertBefore()
- Node.appendChild()
第一個函數(shù)對應于變化后需要進行 Placement 有兄弟節(jié)點的情況腔彰，例如 fiber 從 a,b,c,d 變化為 a,c,b,d叫编。此時 b 被標記為 Placement。react 會找到變化后它的第一個不需要變動的兄弟節(jié)點即為 d霹抛，并調用 parent.insertBefore(d, b) 宵溅。完成后真實的 dom 就從 a,b,c,d 變成 a,c,b,d。
第二個函數(shù)對應于變化后需要進行 Placement 不存在兄弟節(jié)點的情況上炎，例如 fiber 從 a,b,c 變化為 a,c,b 此時 b 被標記為 Placement恃逻，但其不存在兄弟節(jié)點。react 會調用 parent.appendChild(b) 藕施。完成后真實的 dom 就從 a,b,c 變成 a,c,b寇损。
當然，真實的情況比這要更復雜裳食。因此插入 dom 必定要先找到 fiber 樹中真正的 dom 節(jié)點矛市。而 fiber 樹實際上是用戶自定義組件 fiber 以及真實 dom fiber 組合在一起的，如何找到真實的兄弟 dom 節(jié)點對應的 fiber 也是一個比較復雜的任務诲祸。
一點擴展
react 通過 diff 算法來進行性能優(yōu)化浊吏，減少 dom 的創(chuàng)建和刪除。那么 react 采用的優(yōu)化是否為 最優(yōu)化呢救氯？答案是：否找田。例如存在這樣一個特殊的例子：
before: 1, 2, 3, ..., 999
now: 999, 1, 2, 3, ..., 998
由于 react diff 算法的局限，這里需要將 1 從 998 移動到 999 之后着憨，但實際上我們一眼就能看出最簡單的方法是將 999 移動到 1 之前墩衙。這也就是最近很多框架開始使用最長上升子序列來優(yōu)化 diff 算法的原因。那么問題來了甲抖，你知道為什么這里 react 需要移動 998 個元素漆改，或者說為什么最長上升子序列可以解決整個問題嗎?
