react diff算法源碼解析

更新時間：2021年04月10日 11:46:46 作者：zhangyu

這篇文章主要介紹了react diff算法源碼解析的相關(guān)資料，幫助大家更好的理解和學(xué)習(xí)使用react，感興趣的朋友可以了解下

React中Diff算法又稱為調(diào)和算法，對應(yīng)函數(shù)名為reconcileChildren，它的主要作用是標(biāo)記更新過程中那些元素發(fā)生了變化，這些變化包括新增、移動、刪除。過程發(fā)生在beginWork階段，只有非初次渲染才會Diff。

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

節(jié)點Diff又分為兩種：

單節(jié)點Diff —— Element、Portal、string、number。
多節(jié)點Diff —— Array、Iterator。

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

單節(jié)點Diff

單節(jié)點Diff比較簡單，只有key相同并且type相同的情況才會嘗試復(fù)用節(jié)點，否則會返回新的節(jié)點。

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

reconcileSingleElement

  // 單節(jié)點比較
  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é)點
    let child = currentFirstChild;
    while (child !== null) {
      // key相同的情況才diff
      if (child.key === key) {
        switch (child.tag) {
          // ...
          default: {
            // 當(dāng)前fiber和reactElement的type相同時
            if (child.elementType === element.type) {
              // 刪除同級的其他節(jié)點
              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é)點
        deleteRemainingChildren(returnFiber, child);
        break;
      } else {
        // key不同直接刪除節(jié)點
        deleteChild(returnFiber, child);
      }
      child = child.sibling;
    }

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

多節(jié)點Diff

源碼中將多節(jié)點分為了數(shù)組節(jié)點和可迭代節(jié)點。

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

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

對應(yīng)的Diff函數(shù)分別是reconcileChildrenArray和reconcileChildrenIterator。它們的核心Diff邏輯是相同的，所以只分析數(shù)組節(jié)點的Diff —— reconcileChildrenArray函數(shù)。

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

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

第一輪遍歷只針對key和順序都相同的情況，這些key對應(yīng)的節(jié)點位置沒有發(fā)生改變，只需要做更新操作，一旦遍歷遇到key不同的情況就需要跳出循環(huán)。

// 舊節(jié)點
<li key="0"/>
<li key="1"/>
<li key="2"/>
// 新節(jié)點
<li key="0"/>
<li key="1"/>
<li key="5"/>

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

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

新節(jié)點數(shù)量少于舊節(jié)點數(shù)量，這時候需要把多余的舊節(jié)點標(biāo)記為刪除。
新節(jié)點數(shù)量大于舊節(jié)點數(shù)量，這時候需要把多余的新節(jié)點標(biāo)記為新增。

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

// 舊節(jié)點
<li key="0"/>
<li key="1"/>
<li key="2"/>
// 新節(jié)點
<li key="0"/>
<li key="2"/>
<li key="1"/>

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

第二輪的遍歷會稍微復(fù)雜一點，后文在細講。

詳細的代碼如下。

reconcileChildrenArray

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

    // oldFiber為鏈表
    let oldFiber = currentFirstChild;
    // 用來判斷節(jié)點是否移動
    let lastPlacedIndex = 0;
    let newIdx = 0;
    let nextOldFiber = null;
    // 第一輪遍歷，只遍歷key相同的節(jié)點
    for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
      if (oldFiber.index > newIdx) {
        nextOldFiber = oldFiber;
        oldFiber = null;
      } else {
        // 每次循環(huán)舊的fiber節(jié)點都會指向兄弟元素也就是下次循環(huán)的fiber節(jié)點
        nextOldFiber = oldFiber.sibling;
      }
      // key相同返回fiber節(jié)點，key不同返回null
      // 如果type相同復(fù)用節(jié)點，不同返回新節(jié)點
      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é)點，說明type不同創(chuàng)建了新fiber節(jié)點
      if (oldFiber && newFiber.alternate === null) {
        // 需要把oldFiber標(biāo)記刪除
        deleteChild(returnFiber, oldFiber);
      }
      // 放置節(jié)點,更新lastPlacedIndex
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      // 組成新fiber節(jié)點鏈
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
      oldFiber = nextOldFiber;
    }

    /*
    第一輪遍歷完后新節(jié)點數(shù)量少于舊節(jié)點數(shù)量
    newChildren已經(jīng)遍歷完，刪除掉剩下的fiber節(jié)點，可能情況如下 ⬇️
    以前
    <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;
    }

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

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

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

    return resultingFirstChild;
  }

第一輪遍歷比較好理解，這里再細分析一下第二輪遍歷，因為第二輪會出現(xiàn)復(fù)用是否需要移動的問題。

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

接下來的遍歷依然是使用的新節(jié)點為遍歷對象，每次遍歷使用新節(jié)點的key從Map中取出舊節(jié)點來對比是否能復(fù)用，對應(yīng)的函數(shù)為updateFromMap。

如果節(jié)點存在alternate屬性，則是復(fù)用的節(jié)點，這時候需要將它從existingChildren里移除，后續(xù)會把第二輪遍歷完后依然存在在existingChildren里的節(jié)點標(biāo)記為刪除。

如何判斷節(jié)點移動了？

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

當(dāng)復(fù)用的節(jié)點oldIndex小于lastPlacedIndex時，則為移動，如果不需要移動，則會將lastPlacedIndex更新為較大的oldIndex，下一個節(jié)點會以新值判斷，代碼如下：

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

舉個例子：

// 舊
abcd
// 新
acbd

abcd均為key值。

第一輪遍歷后剩下的需要對比節(jié)點:

// 舊
bcd
// 新
cbd

a節(jié)點在第一輪已經(jīng)復(fù)用，并且調(diào)用過placeChild，這時lastPlacedIndex值為0。

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

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

由這個例子可以看出，React中將右側(cè)不需要移動的節(jié)點作為參照，將需要移動的節(jié)點都是統(tǒng)一從左向右移動的。

在后續(xù)Layout階段會將這里標(biāo)記了Placement的節(jié)點做insertBefore操作。