React Diff算法详解

基本概览

React 16以后的Diff算法是以Fiber架构为基础的，这个Diff算法的输入为旧Fiber子节点和JSX节点或节点数组，输出为新的Fiber子节点以及Fiber子节点所对应的副作用链表（副作用为增加、删除、移动等）。

Diff算法的核心函数为 reconcileChildFibers ，函数内分为三种处理情况：

1. 新的children为单个JSX对象：进入单节点diff逻辑
2. 新的children为字符串或者数字：进入单节点diff逻辑
3. 新的children为数组或者迭代器：进入多节点diff逻辑

function reconcileChildFibers(
 returnFiber: Fiber,
 currentFirstChild: Fiber | null,
 newChild: any,
 lanes: Lanes,
): Fiber | null {
  const isUnkeyedTopLevelFragment =
        typeof newChild === 'object' &&
        newChild !== null &&
        newChild.type === REACT_FRAGMENT_TYPE &&
        newChild.key === null;
  if (isUnkeyedTopLevelFragment) {
    newChild = newChild.props.children;
  }
  const isObject = typeof newChild === 'object' && newChild !== null;
    // 对象
  if (isObject) {
    switch (newChild.$$typeof) {
      case REACT_ELEMENT_TYPE:
        return placeSingleChild(
          reconcileSingleElement(
            returnFiber,
            currentFirstChild,
            newChild,
            lanes,
          ),
        );
      case REACT_PORTAL_TYPE:
        return placeSingleChild(
          reconcileSinglePortal(
            returnFiber,
            currentFirstChild,
            newChild,
            lanes,
          ),
        );
      case REACT_LAZY_TYPE:
        if (enableLazyElements) {
          const payload = newChild._payload;
          const init = newChild._init;
          // TODO: This function is supposed to be non-recursive.
          return reconcileChildFibers(
            returnFiber,
            currentFirstChild,
            init(payload),
            lanes,
          );
        }
    }
  }
    // 字符串或者数值
  if (typeof newChild === 'string' || typeof newChild === 'number') {
    return placeSingleChild(
      reconcileSingleTextNode(
        returnFiber,
        currentFirstChild,
        '' + newChild,
        lanes,
      ),
    );
  }
  // 数组
    if (isArray(newChild)) {
    return reconcileChildrenArray(
      returnFiber,
      currentFirstChild,
      newChild,
      lanes,
    );
  }
  ...
  return deleteRemainingChildren(returnFiber, currentFirstChild);
}

以下将分别对单节点和多节点两种情况进行分析

相关工具函数

deleteChild(returnFiber, childToDelete)

任务有几个：

1. 为childToDelete打上 Deletion 标签
2. 添加childToDelete到returnFiber的副作用链表

3. 添加childToDelete到returnFiber的deletions数组，并且给returnFiber打上 ChildDeletion 标签

   deleteRemainingChildren(returnFiber, currentFirstChild)

   对从currentFirstChild开始的节点执行deleteChild操作

   placeChild(newFiber, lastPlacedIndex, newIndex)

4. 将 newIndex 赋值给 newFiber.index

5. 判断新Fiber节点的alternate属性
   1. 如果存在，那么说明此节点为复用，复用有两种情况：
      1. 旧Fiber节点的索引小于lastPlacedIndex：标记为 Placement ，lastPlacedIndex不变
      2. 旧Fiber节点的索引大于等于lastPlacedIndex：无需移动，lastPlacedIndex变更为旧Fiber的旧index
   2. 如果不存在，那么说明此节点为新创建的插入：将节点标记为 Placement ，lastPlacedIndex不变

lastPlacedIndex可以理解为当前已经遍历到的被复用的旧Fiber节点的**最大旧索引值**

想要完全理解上面的逻辑就要明确在commit阶段React处理Placement时候的策略，为了便于理解，仅仅以HostComponent为例子，commitPlacement的逻辑如下：

1. getHostParentFiber：找到父级HostComponent节点
2. getHostSibling：找到临近的HostComponent节点，且此节点没有Placement标签，这里称之为稳定节点
   1. 如果有，那么采用insertBefore插入到此节点前
   2. 如果没有，那么采用appendChild插入到末端

diff遍历过程如下：

1. 节点2被复用，lastPlacedIndex更新为2，节点2为稳定节点
2. 节点1被复用，由于index为1小于2，需要被移动，因此打上Placement标签
3. 节点3被复用，index为3大于2，lastPlacedIndex更新为3，节点3为稳定节点
4. 节点0被复用，index为0小于3，需要被移动，因此打上Placement标签

   单节点Diff

   单节点Diff的核心函数是 placeSingleChild ，这个函数的作用是接受一个Fiber节点，然后将其 flags 属性设定为 Placement 。而newChild为对象和数值/字符串两种情况，其区别就在于生成Fiber节点的函数不同。

   newChild为对象

   针对newChild为对象的情况，其生成Fiber节点的函数为 reconcileSingleElement 。这个函数的基本思路是遍历旧的Fiber节点：

• 如果存在可复用的节点，那么就复用它，并且调用 deleteRemainingChildren 删除剩余节点
• 如果遍历完毕后都没发现有可复用的节点，那么就创建一个新的节点

其中可复用的fiber标准有两个：

1. fiber的key值一致
2. fiber的tag值一致

   newChild为数值/字符串

   针对newChild为数值/字符串的情况，其生成Fiber节点的函数为 reconcileTextNode 。这种情况一般发生在类组件或者函数组件的返回值为数值/字符串的时候，因为针对HostComponent的情况，React会有针对性优化。

情况与对象类似，但是只会检查旧Fiber的第一个节点是否为文字节点

• 如果是，则复用，并且对剩余节点执行deleteRemainingChildren
• 如果不是，则对所有子节点执行deleteRemainingChildren，并且创建一个新节点

  总结

  单节点Diff的总体思路如下：

1. 从旧Fiber子节点中查找可复用的Fiber节点，如果存在就复用，如果不存在就新建
2. 将剩余的Fiber节点标记为 Deletion ，且添加到父节点的副作用链表中
3. 将新的Fiber节点标记为 Placement

   多节点Diff

   多节点Diff为整个diff算法的核心内容，核心函数为 reconcileChildrenArray 。在这个函数中，总共会经历两轮遍历，直至newChildren被遍历完毕。

   第一轮遍历

   for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
   if (oldFiber.index > newIdx) {
    nextOldFiber = oldFiber;
    oldFiber = null;
   } else {
    nextOldFiber = oldFiber.sibling;
   }
   const newFiber = updateSlot(
    returnFiber,
    oldFiber,
    newChildren[newIdx],
    lanes,
   );
   if (newFiber === null) {
    if (oldFiber === null) {
      oldFiber = nextOldFiber;
    }
    break;
   }
   if (shouldTrackSideEffects) {
    // 旧Fiber没有被复用，执行删除操作
    if (oldFiber && newFiber.alternate === null) {
      deleteChild(returnFiber, oldFiber);
    }
   }
   lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
   if (previousNewFiber === null) {
    resultingFirstChild = newFiber;
   } else {
    previousNewFiber.sibling = newFiber;
   }
   previousNewFiber = newFiber;
   oldFiber = nextOldFiber;
   }

   updateSlot

   updateSlot函数作用是对比旧fiber和新的JSX节点，生成新的Fiber节点。

根据当前遍历到的newChild类型（也就是JSX节点）分为三种情况：

1. string/number
   1. 如果旧fiber的key值为null，则调用updateTextNode函数
   2. 如果旧fiber的key值不为null，则返回null
2. 对象：（此处还有portal和lazy两种类型，暂不讨论）
   1. 如果旧fiber与当前JSX节点key值不一致，则返回null
   2. 如果旧fiber与当前JSX节点key值一致，则调用updateElement
3. 数组：调用updateFragment

对于上面的updateTextNode, updateElement, updateFragment等函数，代码逻辑基本一致：

1. 如果旧fiber节点存在而且跟newChild的类型一致，那么就可以复用旧fiber节点（核心函数useFiber）。这里的复用并非是直接引用旧Fiber对象，而是根据旧Fiber对象克隆一个新的Fiber对象。
2. 如果旧fiber节点不存在或者跟newChild的类型不一致，那么就新创建fiber节点（核心函数createFiberFrom…）

上述两者最为核心的差别在于复用的Fiber节点的alternate属性会指向旧Fiber节点，而新创建的节点的alternate属性则会指向null，后面的函数将会以此为依据判断是否对旧Fiber节点执行删除操作。

判断是否跳出循环

如果updateSlot的返回值是null，则会直接跳出第一轮循环，其实就是key值不匹配时跳出循环。

删除旧Fiber节点

新的Fiber节点如果不存在alternate，意味着没有被复用，此时旧Fiber节点应该被删除。

插入新Fiber节点

调用placeChild函数插入新创建的节点

第二轮遍历

此时存在三种情况：

1. 新节点遍历完毕：删除剩余的旧节点并返回
2. 新节点没遍历完毕，旧节点遍历完毕：添加剩余的新节点并返回
3. 新旧节点都没遍历完毕：以下详细讨论

针对新旧节点都没遍历完毕的情况，React会对剩余的旧Fiber节点建立一个哈希表 existingChildren ，表的键名分为两类：

1. key值
2. 旧Fiber的索引index

如果Fiber节点key不为null，那么其键名就为key，否则就为索引index

接着React会遍历剩余的新节点，尝试根据新节点的key或者index从 existingChilren 中找出可被复用的节点，如果可复用，那么将旧节点从哈希表中删除。

当新节点遍历完毕后，React会将 existingChildren 剩余的节点全部执行 deleteChild 操作。

到此，diff算法执行完毕。

实例分析

单节点实例

实例1

// before
<div>3</div>
<div>4</div>
// after
<p>1</p>

• reconcileChildFibers 判断newChild类型为Object，进入 reconcileSingleElement 函数
• 遍历旧节点，发现第一个节点key值与p都为null，但是tag不一致，执行 deleteRemainingChildren 删除所有旧节点，停止遍历，返回新创建的Fiber节点。

• placeSingleChild 给新创建的节点打上 Placement 的标签

  实例2

  // before
  <div>3</div>
  <p key="a">4</p>
  // after
  <p key="a">1</p>

• reconcileChildFibers 判断newChild类型为Object，进入 reconcileSingleElement 函数

• 遍历旧节点，第一个节点key值与当前key值不匹配，执行 deleteChild 删除当前旧节点
• 继续遍历，第二个节点的key值与当前key值一致，且tag也一致，执行 useFiber 函数复用节点，并且删除剩余旧节点
• placeSingleChild 给新创建的节点打上 Placement 的标签

  多节点实例

  只会执行第一轮遍历的情况

  ```html // before
  3
  4

// after

1

// after

1. reconcileChildFibers 判断newChild类型为Array，进入 reconcileChildrenArray 函数
2. 进入第一轮循环

执行updateSlot得到newFiber div:1 。当前JSX为 ReactElement ，并且新旧key值都为null，执行 updateElement 。在updateElement中，由于新旧节点的tag一致，所以复用Fiber，其alternate属性为 div:3 的旧Fiber节点。

由于 newFiber.alternate 不为为null，所以为复用的节点，因此不执行 deleteChild 。

执行 placeChild 插入新节点。

执行 updateSlot ，由于key值不相同，所以返回null，接着跳出第一轮循环。

1. 创建 existingChilren 哈希表

1. 遍历剩余的newChild

遍历 div:c ，根据 existingChildren 查得对应节点，复用，并且将其从哈希表中删除，执行 placeChild 。

遍历 div:a ，根据 existingChildren 查得对应节点，复用，并且将其从哈希表中删除，执行 placeChild 。

遍历 div:b ，根据 existingChildren 查得对应节点，复用，并且将其从哈希表中删除，执行 placeChild 。

1. 删除剩余节点，发现 existingChildren 已经为空，因此直接返回。