react diff算法源碼解析

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

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

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

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

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

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

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

單節(jié)點(diǎn)Diff

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

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

reconcileSingleElement

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

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

多節(jié)點(diǎn)Diff

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

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

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

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

這一段的代碼比較長(zhǎng)，但邏輯很清晰，從分割線(xiàn)分為兩輪遍歷。

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

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

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

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

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

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

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

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

// 第二輪遍歷對(duì)比<li key="2"/>、<li key="1"/>這兩個(gè)節(jié)點(diǎn)

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

詳細(xì)的代碼如下。

reconcileChildrenArray

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

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

    /*
    第一輪遍歷完后新節(jié)點(diǎn)數(shù)量少于舊節(jié)點(diǎn)數(shù)量
    newChildren已經(jīng)遍歷完，刪除掉剩下的fiber節(jié)點(diǎn)，可能情況如下 ⬇️
    以前
    <li key="0"/>
    <li key="1"/>
    <li key="2"/>
    新的
    <li key="0"/>
    <li key="1"/>
    就會(huì)把<li key="2"/>刪除
     */
    if (newIdx === newChildren.length) {
      deleteRemainingChildren(returnFiber, oldFiber);
      return resultingFirstChild;
    }

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

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

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

    return resultingFirstChild;
  }

第一輪遍歷比較好理解，這里再細(xì)分析一下第二輪遍歷，因?yàn)榈诙啎?huì)出現(xiàn)復(fù)用是否需要移動(dòng)的問(wèn)題。

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

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

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

如何判斷節(jié)點(diǎn)移動(dòng)了？

這里存在一個(gè)變量lastPlacedIndex用來(lái)判斷節(jié)點(diǎn)是否移動(dòng)，每次將節(jié)點(diǎn)添加到新的Fiber鏈表中，都會(huì)更新這個(gè)值。

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

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

舉個(gè)例子：

// 舊
abcd
// 新
acbd

abcd均為key值。

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

// 舊
bcd
// 新
cbd

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

進(jìn)入第二輪遍歷，依然是以新節(jié)點(diǎn)為遍歷對(duì)象。

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

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

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