react diff算法源碼解析

Posted on by

React中Diff算法又稱為調和算法，對應函數名為reconcileChildren，它的主要作用是標記更新過程中那些元素發生瞭變化，這些變化包括新增、移動、刪除。過程發生在beginWork階段，隻有非初次渲染才會Diff。

以前看過一些文章將Diff算法表述為兩顆Fiber樹的比較，這是不正確的，實際的Diff過程是一組現有的Fiber節點和新的由JSX生成的ReactElement的比較，然後生成新的Fiber節點的過程，這個過程中也會嘗試復用現有Fiber節點。

節點Diff又分為兩種：

  1. 單節點Diff —— Element、Portal、string、number。
  2. 多節點Diff —— Array、Iterator。

以下React版本為17.0.1，代碼文件為ReactChildFiber.old.js。

單節點Diff

單節點Diff比較簡單，隻有key相同並且type相同的情況才會嘗試復用節點，否則會返回新的節點。

單節點大部分情況下我們都不會去賦值key，所以它們默認為null，也是相同的。

reconcileSingleElement

  // 單節點比較
  function reconcileSingleElement(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    element: ReactElement,
    lanes: Lanes,
  ): Fiber {
    // 當前新的reactElement的key
    const key = element.key;
    // 當前的child fiber節點
    let child = currentFirstChild;
    while (child !== null) {
      // key相同的情況才diff
      if (child.key === key) {
        switch (child.tag) {
          // ...
          default: {
            // 當前fiber和reactElement的type相同時
            if (child.elementType === element.type) {
              // 刪除同級的其他節點
              deleteRemainingChildren(returnFiber, child.sibling);
              // 復用當前child fiber
              const existing = useFiber(child, element.props);
              existing.ref = coerceRef(returnFiber, child, element);
              existing.return = returnFiber;
              // 返回可復用的child fiber
              return existing;
            }
            break;
          }
        }
        // 不匹配刪除節點
        deleteRemainingChildren(returnFiber, child);
        break;
      } else {
        // key不同直接刪除節點
        deleteChild(returnFiber, child);
      }
      child = child.sibling;
    }

    // 新的Fiber節點
    const created = createFiberFromElement(element, returnFiber.mode, lanes);
    created.ref = coerceRef(returnFiber, currentFirstChild, element);
    created.return = returnFiber;
    return created;
  }

多節點Diff

源碼中將多節點分為瞭數組節點和可迭代節點。

if (isArray(newChild)) {
  return reconcileChildrenArray(
    returnFiber,
    currentFirstChild,
    newChild,
    lanes,
  );
}

if (getIteratorFn(newChild)) {
  return reconcileChildrenIterator(
    returnFiber,
    currentFirstChild,
    newChild,
    lanes,
  );
}

對應的Diff函數分別是reconcileChildrenArray和reconcileChildrenIterator。它們的核心Diff邏輯是相同的，所以隻分析數組節點的Diff —— reconcileChildrenArray函數。

這一段的代碼比較長，但邏輯很清晰，從分割線分為兩輪遍歷。

  • 第一輪遍歷的是順序相同且key也相同的節點，這些節點需要做更新操作。
  • 第二輪遍歷的是順序不同，可能key也不同的節點，這些節點需要做新增、移動或刪除操作。

第一輪遍歷隻針對key和順序都相同的情況，這些key對應的節點位置沒有發生改變，隻需要做更新操作，一旦遍歷遇到key不同的情況就需要跳出循環。

// 舊節點
<li key="0"/>
<li key="1"/>
<li key="2"/>
// 新節點
<li key="0"/>
<li key="1"/>
<li key="5"/>

// key="5"不同，跳出遍歷
// 第一輪遍歷的節點
<li key="0"/>
<li key="1"/>
// <li key="2"/>和<li key="5"/>留在第二輪遍歷比較。

在第一輪遍歷完後也分為兩種情況。

  1. 新節點數量少於舊節點數量，這時候需要把多餘的舊節點標記為刪除。
  2. 新節點數量大於舊節點數量，這時候需要把多餘的新節點標記為新增。

第二輪遍歷針對key不同或順序不同的情況，可能情況如下：

// 舊節點
<li key="0"/>
<li key="1"/>
<li key="2"/>
// 新節點
<li key="0"/>
<li key="2"/>
<li key="1"/>

// 第二輪遍歷對比<li key="2"/>、<li key="1"/>這兩個節點

第二輪的遍歷會稍微復雜一點，後文在細講。

詳細的代碼如下。

reconcileChildrenArray

  function reconcileChildrenArray(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    newChildren: Array<*>,
    lanes: Lanes,
  ): Fiber | null {
    // 函數返回的Fiber節點
    let resultingFirstChild: Fiber | null = null;
    let previousNewFiber: Fiber | null = null;

    // oldFiber為鏈表
    let oldFiber = currentFirstChild;
    // 用來判斷節點是否移動
    let lastPlacedIndex = 0;
    let newIdx = 0;
    let nextOldFiber = null;
    // 第一輪遍歷，隻遍歷key相同的節點
    for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
      if (oldFiber.index > newIdx) {
        nextOldFiber = oldFiber;
        oldFiber = null;
      } else {
        // 每次循環舊的fiber節點都會指向兄弟元素也就是下次循環的fiber節點
        nextOldFiber = oldFiber.sibling;
      }
      // key相同返回fiber節點，key不同返回null
      // 如果type相同復用節點，不同返回新節點
      const newFiber = updateSlot(
        returnFiber,
        oldFiber,
        newChildren[newIdx],
        lanes,
      );
      // newFiber為null表示key不同，跳出循環
      if (newFiber === null) {
        if (oldFiber === null) {
          oldFiber = nextOldFiber;
        }
        break;
      }
      // newFiber.alternate為null就是新節點，說明type不同創建瞭新fiber節點
      if (oldFiber && newFiber.alternate === null) {
        // 需要把oldFiber標記刪除
        deleteChild(returnFiber, oldFiber);
      }
      // 放置節點,更新lastPlacedIndex
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      // 組成新fiber節點鏈
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
      oldFiber = nextOldFiber;
    }

    /*
    第一輪遍歷完後新節點數量少於舊節點數量
    newChildren已經遍歷完，刪除掉剩下的fiber節點，可能情況如下 ⬇️
    以前
    <li key="0"/>
    <li key="1"/>
    <li key="2"/>
    新的
    <li key="0"/>
    <li key="1"/>
    就會把<li key="2"/>刪除
     */
    if (newIdx === newChildren.length) {
      deleteRemainingChildren(returnFiber, oldFiber);
      return resultingFirstChild;
    }

    /*
    第一輪遍歷完新節點數量大於舊節點數量
    oldFiber已經遍歷完，可能情況如下 ⬇️
    以前
    <li key="0"/>
    <li key="1"/>
    新的
    <li key="0"/>
    <li key="1"/>
    <li key="2"/>
    就會添加新的<li key="2"/>，這一段是新節點的插入邏輯
     */
    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節點鏈
        if (previousNewFiber === null) {
          resultingFirstChild = newFiber;
        } else {
          previousNewFiber.sibling = newFiber;
        }
        previousNewFiber = newFiber;
      }
      return resultingFirstChild;
    }
      
    // ---------------------------------------------------------------------

    // 用剩餘的oldFiber創建一個key->fiber節點的Map，方便用key來獲取對應的舊fiber節點
    const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
    
    // 第二輪遍歷，繼續遍歷剩餘的節點，這些節點可能是需要移動或者刪除的
    for (; newIdx < newChildren.length; newIdx++) {
      // 從map中獲取對應對應key的舊節點，返回更新後的新節點
      const newFiber = updateFromMap(
        existingChildren,
        returnFiber,
        newIdx,
        newChildren[newIdx],
        lanes,
      );
      if (newFiber !== null) {
        // 復用的新節點，從map裡刪除老的節點，對應的情況可能是位置的改變
        if (newFiber.alternate !== null) {
          // 復用的節點要移除map，因為map裡剩餘的節點都會被標記Deletion刪除
          existingChildren.delete(
            newFiber.key === null ? newIdx : newFiber.key,
          );
        }
        // 放置節點同時節點判斷是否移動
        lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
        if (previousNewFiber === null) {
          resultingFirstChild = newFiber;
        } else {
          previousNewFiber.sibling = newFiber;
        }
        previousNewFiber = newFiber;
      }
    }

    // 刪除剩下的無用節點
    existingChildren.forEach(child => deleteChild(returnFiber, child));

    return resultingFirstChild;
  }

第一輪遍歷比較好理解，這裡再細分析一下第二輪遍歷，因為第二輪會出現復用是否需要移動的問題。

第二輪遍歷首先遍歷剩餘的oldFiber，組成一個key -> 舊fiber節點的Map，這用可以通過key來快速的獲取舊節點。

接下來的遍歷依然是使用的新節點為遍歷對象，每次遍歷使用新節點的key從Map中取出舊節點來對比是否能復用，對應的函數為updateFromMap。

如果節點存在alternate屬性，則是復用的節點，這時候需要將它從existingChildren裡移除，後續會把第二輪遍歷完後依然存在在existingChildren裡的節點標記為刪除。

如何判斷節點移動瞭？

這裡存在一個變量lastPlacedIndex用來判斷節點是否移動，每次將節點添加到新的Fiber鏈表中，都會更新這個值。

當復用的節點oldIndex小於lastPlacedIndex時，則為移動，如果不需要移動，則會將lastPlacedIndex更新為較大的oldIndex，下一個節點會以新值判斷，代碼如下：

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) {
 			// 節點移動
      newFiber.flags = Placement;
      return lastPlacedIndex;
    } else {
      // 節點位置無變化
      return oldIndex;
    }
  } else {
    // 插入的新節點
    newFiber.flags = Placement;
    return lastPlacedIndex;
  }
}

舉個例子：

// 舊
abcd
// 新
acbd

abcd均為key值。

第一輪遍歷後剩下的需要對比節點:

// 舊
bcd
// 新
cbd

a節點在第一輪已經復用，並且調用過placeChild，這時lastPlacedIndex值為0。

進入第二輪遍歷，依然是以新節點為遍歷對象。

c => 在舊節點中存在，可復用，它的index在舊節點中為2，2 > lastPlacedIndex(0)，不需要移動,將lastPlacedIndex賦值為2。
b => 在舊節點中存在，可復用，它的index在舊節點中為1，1 < lastPlacedIndex(2)，需要移動，標記Placement。
d => 在舊節點中存在，可復用，它的index在舊節點中為3，3 > lastPlacedIndex(2)，不需要移動。

由這個例子可以看出，React中將右側不需要移動的節點作為參照，將需要移動的節點都是統一從左向右移動的。

在後續Layout階段會將這裡標記瞭Placement的節點做insertBefore操作。

總結

React中的Diff算法核心代碼不算很長，但是卻引入key巧妙的將復雜度由O(n3 )變為瞭O(n)。

碼農內卷太嚴重，所以不得不學習源碼瞭。

以上就是react diff算法源碼解析的詳細內容，更多關於react diff算法的資料請關註WalkonNet其它相關文章！

推薦閱讀：

    None Found