react Diff 算法

[mbaxszy7]

react Diff 算法

react Diff 操作在哪个阶段?

react Diff 操作发生在render阶段产出workInProgress fiber节点的时候，会根据current fiber tree 和本次要更新节点进行diff，同时会标记effect tag（在effect list fiber tree 上）。

    workInProgress.child = reconcileChildFibers(
      workInProgress,
      current.child,
      nextChildren,
      renderExpirationTime,
    );

reconcileChildFibers就是diff算法的入口函数

react Diff 是如何做优化的？

• 正常的两棵树diff的时间复杂度是O(n^3) ，在React官网文档Reconciliation上有提到。
  O(n^3) 的大致由来： 两棵树嵌套循环寻找不同的节点：O(n^2)，寻找到不同的节点后，需要再遍历得到最小的转换消耗，最终得 到O(n^3)

• React基于两个假设实现了一种启发式O（n）算法

1. 不同类型的两个元素将产生不同的树。
2. 开发人员可以使用key prop 提示哪些子元素在不同的渲染中可能是稳定的。

• 最终React Diff 算法的优化

1. 只对同层节点进行比较
2. 不同类型的元素直接删除，然后重新创建新的元素
3. 相同类型的DOM元素，React会查看两者的属性，仅更新更改的属性
4. 相同类型的组件元素，组件实例保持不变。React会更新组件的props
5. 多个子元素的情况下，React引入key prop，使用key将原始树中的子代与后一棵树中的子代进行匹配，对子元素进行重用。

按照这样的优化，最终只需一层遍历O(n)即可完成

react Diff 源码浅析

 function reconcileChildFibers(
    // 父节点fiber
    returnFiber: Fiber,
    // 父节点fiber的第一个child fiber
    currentFirstChild: Fiber | null,
    // 新产生的节点信息
    newChild: any,
    expirationTime: ExpirationTime,
  ): Fiber | null {
    // 处理<>{[...]}</> and <>...</> 直接取fragment的children
    const isUnkeyedTopLevelFragment =
      typeof newChild === 'object' &&
      newChild !== null &&
      newChild.type === REACT_FRAGMENT_TYPE &&
      newChild.key === null;
    if (isUnkeyedTopLevelFragment) {
      newChild = newChild.props.children;
    }

    // Handle object types
    const isObject = typeof newChild === 'object' && newChild !== null;

    if (isObject) {
      switch (newChild.$$typeof) {
        // React.createElement
        case REACT_ELEMENT_TYPE:
          return placeSingleChild(
            reconcileSingleElement(
              returnFiber,
              currentFirstChild,
              newChild,
              expirationTime,
            ),
          );
        // ReactDOM.createPortal
        case REACT_PORTAL_TYPE:
          return placeSingleChild(
            reconcileSinglePortal(
              returnFiber,
              currentFirstChild,
              newChild,
              expirationTime,
            ),
          );
      }
    }

    if (typeof newChild === 'string' || typeof newChild === 'number') {
      // 文本
      return placeSingleChild(
        reconcileSingleTextNode(
          returnFiber,
          currentFirstChild,
          '' + newChild,
          expirationTime,
        ),
      );
    }

    if (isArray(newChild)) {
      // 数组
      return reconcileChildrenArray(
        returnFiber,
        currentFirstChild,
        newChild,
        expirationTime,
      );
    }

    if (getIteratorFn(newChild)) {
      // generator
      return reconcileChildrenIterator(
        returnFiber,
        currentFirstChild,
        newChild,
        expirationTime,
      );
    }

   ......

    // 删除没有匹配的子节点
    return deleteRemainingChildren(returnFiber, currentFirstChild);
  }

通过判断新节点（newChild）的类型，匹配不同的diff操作。

1. REACT_ELEMENT_TYPE。由React.createElement 产生，是单子元素节点，diff操作reconcileSingleElement
2. REACT_PORTAL_TYPE。由ReactDOM.createPortal 产生，是单子元素节点，diff操作reconcileSinglePortal
3. "string" "number"。文本节点，是单子元素节点，diff操作reconcileSingleTextNode
4. 数组子元素。diff操作reconcileChildrenArray
5. 可迭代子元素（比如generator）。diff操作reconcileChildrenIterator

最后对没有匹配的到newChild节点的old子节点进行删除操作

reconcileSingleElement

详细注释

function reconcileSingleElement(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    element: ReactElement,
    expirationTime: ExpirationTime,
  ): Fiber {
    // 要更新的child的key
    const key = element.key;
    // current child
    let child = currentFirstChild;
    // 取第一个不为null的current child
    while (child !== null) {
      // 判断current child 和 要更新的child的key 是否相等
      if (child.key === key) {
        switch (child.tag) {
          case Fragment: {
            if (element.type === REACT_FRAGMENT_TYPE) {
              // "删除" current child 的 sibling
              deleteRemainingChildren(returnFiber, child.sibling);
              // 复用current child， 传入要更新的child的props
              const existing = useFiber(child, element.props.children);
              existing.return = returnFiber;
              if (__DEV__) {
                existing._debugSource = element._source;
                existing._debugOwner = element._owner;
              }
              return existing;
            }
            break;
          }
          case Block:
            if (enableBlocksAPI) {
              if (
                element.type.$$typeof === REACT_BLOCK_TYPE &&
                element.type.render === child.type.render
              ) {
                deleteRemainingChildren(returnFiber, child.sibling);
                // 复用current child， 传入要更新的child的props
                const existing = useFiber(child, element.props);
                existing.type = element.type;
                existing.return = returnFiber;
                if (__DEV__) {
                  existing._debugSource = element._source;
                  existing._debugOwner = element._owner;
                }
                return existing;
              }
            }

          default: {
            // type 相同
            if (
              child.elementType === element.type ||
              (__DEV__
                ? isCompatibleFamilyForHotReloading(child, element)
                : false)
            ) {
              deleteRemainingChildren(returnFiber, child.sibling);
              // 复用current child， 传入要更新的child的props
              const existing = useFiber(child, element.props);
              existing.ref = coerceRef(returnFiber, child, element);
              existing.return = returnFiber;
              if (__DEV__) {
                existing._debugSource = element._source;
                existing._debugOwner = element._owner;
              }
              return existing;
            }
            break;
          }
        }
        // "删除" 不能复用的节点
        deleteRemainingChildren(returnFiber, child);
        break;
      } else {
        // key不相等，“删除” current child （标记child的effectTag为Deletion）
        deleteChild(returnFiber, child);
      }
      child = child.sibling;
    }

    // 最终没有可复用的节点，创建节点
    if (element.type === REACT_FRAGMENT_TYPE) {
      const created = createFiberFromFragment(
        element.props.children,
        returnFiber.mode,
        expirationTime,
        element.key,
      );
      created.return = returnFiber;
      return created;
    } else {
      const created = createFiberFromElement(
        element,
        returnFiber.mode,
        expirationTime,
      );
      created.ref = coerceRef(returnFiber, currentFirstChild, element);
      created.return = returnFiber;
      return created;
    }
  }

reconcileChildrenArray

详细注释

 function reconcileChildrenArray(
    // current fiber 父节点
    returnFiber: Fiber,
    // current fiber 的第一个child， 其余child用sibling指针链接 （父节点没有指向非首个子节点的指针）
    currentFirstChild: Fiber | null,
    // 当前要更新的child 数组
    newChildren: Array<*>,
    expirationTime: ExpirationTime,
  ): Fiber | null {
    // 需要返回的结果，当返回时，已经是匹配复用好了的fiber first child，其余child用sibling指针链接
    let resultingFirstChild: Fiber | null = null;
    let previousNewFiber: Fiber | null = null;

    let oldFiber = currentFirstChild;
    // 最后一个可复用节点的index， index指的是current fiber child（oldFiber）对应的index
    let lastPlacedIndex = 0;
    let newIdx = 0;
    let nextOldFiber = null;
    // newChildren第一次循环
    // 处理的是key相同，并且是按顺序的，也就是newChildren 的节点没有改变位置
    // 这一次的循环处理完后，有如下结果
    // 1. newChildren没有遍历完，oldFiber也没有遍历完，待后续处理
    // 2. newChildren 数据已经匹配处理完成, 那就要标记删除oldFiber的节点
    // 3. 没有oldFiber可以复用，那就要新建插入fiber
    for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
      if (oldFiber.index > newIdx) {
        nextOldFiber = oldFiber;
        oldFiber = null;
      } else {
        nextOldFiber = oldFiber.sibling;
      }
      // key相等就复用oldFiber
      const newFiber = updateSlot(
        returnFiber,
        oldFiber,
        newChildren[newIdx],
        expirationTime,
      );
      if (newFiber === null) {
        if (oldFiber === null) {
          oldFiber = nextOldFiber;
        }
        break;
      }
      // shouldTrackSideEffects 非首屏渲染为true， 表示需要标记 workInProgress child的effectTag
      if (shouldTrackSideEffects) {
        // newFiber.alternate ===null 匹配完成
        if (oldFiber && newFiber.alternate === null) {
          //标记删除其余的old fiber child
          deleteChild(returnFiber, oldFiber);
        }
      }
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      // 记录能匹配到的最后一个newFiber child
      previousNewFiber = newFiber;
      // 记录能匹配到的最后一个oldFiber child
      oldFiber = nextOldFiber;
    }
     
    // newChildren 数据已经匹配处理完成
    if (newIdx === newChildren.length) {
      // 标记删除其余的old fiber child
      deleteRemainingChildren(returnFiber, oldFiber);
      return resultingFirstChild;
    }

    if (oldFiber === null) {
      // 没有oldFiber可以复用，新建插入fiber
      for (; newIdx < newChildren.length; newIdx++) {
        const newFiber = createChild(
          returnFiber,
          newChildren[newIdx],
          expirationTime,
        );
        if (newFiber === null) {
          continue;
        }
        lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
        if (previousNewFiber === null) {
          // TODO: Move out of the loop. This only happens for the first run.
          resultingFirstChild = newFiber;
        } else {
          // 用sibling串联newFiber
          previousNewFiber.sibling = newFiber;
        }
        previousNewFiber = newFiber;
      }
      return resultingFirstChild;
    }

    // Add all children to a key map for quick lookups.
    // 处理oldFiber， 转换为一个map， key为oldFiber节点的key， value为oldFiber child
    const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

    // newChildren第二次循环开始
    // 处理的是newChildren的节点位置换了
    // 这里的逻辑有点绕，需要举🌰
    for (; newIdx < newChildren.length; newIdx++) {
      const newFiber = updateFromMap(
        existingChildren,
        returnFiber,
        newIdx,
        newChildren[newIdx],
        expirationTime,
      );
      if (newFiber !== null) {
        if (shouldTrackSideEffects) {
          if (newFiber.alternate !== null) {
            // The new fiber is a work in progress, but if there exists a
            // current, that means that we reused the fiber. We need to delete
            // it from the child list so that we don't add it to the deletion
            // list.
            existingChildren.delete(
              newFiber.key === null ? newIdx : newFiber.key,
            );
          }
        }
        lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
        if (previousNewFiber === null) {
          resultingFirstChild = newFiber;
        } else {
          previousNewFiber.sibling = newFiber;
        }
        previousNewFiber = newFiber;
      }
    }

    if (shouldTrackSideEffects) {
      // Any existing children that weren't consumed above were deleted. We need
      // to add them to the deletion list.
      existingChildren.forEach((child) => deleteChild(returnFiber, child));
    }

    return resultingFirstChild;
  }

第二次循环的例子（🌰来源）

// 之前
abcd

// 之后
acdb

===第一轮遍历开始===
a（之后）vs a（之前）  
key不变，可复用
此时 a 对应的oldFiber（之前的a）在之前的数组（abcd）中索引为0
所以 lastPlacedIndex = 0;

继续第一轮遍历...

c（之后）vs b（之前）  
key改变，不能复用，跳出第一轮遍历
此时 lastPlacedIndex === 0;
===第一轮遍历结束===

===第二轮遍历开始===
newChildren === cdb，没用完，不需要执行删除旧节点
oldFiber === bcd，没用完，不需要执行插入新节点

将剩余oldFiber（bcd）保存为map

// 当前oldFiber：bcd
// 当前newChildren：cdb

继续遍历剩余newChildren

key === c 在 oldFiber中存在
const oldIndex = c（之前）.index;
即 oldIndex 代表当前可复用节点（c）在上一次更新时的位置索引
此时 oldIndex === 2;  // 之前节点为 abcd，所以c.index === 2
比较 oldIndex 与 lastPlacedIndex;

如果 oldIndex >= lastPlacedIndex 代表该可复用节点不需要移动
并将 lastPlacedIndex = oldIndex;
如果 oldIndex < lastplacedIndex 该可复用节点之前插入的位置索引小于这次更新需要插入的位置索引，代表该节点需要向右移动

在例子中，oldIndex 2 > lastPlacedIndex 0，
则 lastPlacedIndex = 2;
c节点位置不变

继续遍历剩余newChildren

// 当前oldFiber：bd
// 当前newChildren：db

key === d 在 oldFiber中存在
const oldIndex = d（之前）.index;
oldIndex 3 > lastPlacedIndex 2 // 之前节点为 abcd，所以d.index === 3
则 lastPlacedIndex = 3;
d节点位置不变

继续遍历剩余newChildren

// 当前oldFiber：b
// 当前newChildren：b

key === b 在 oldFiber中存在
const oldIndex = b（之前）.index;
oldIndex 1 < lastPlacedIndex 3 // 之前节点为 abcd，所以b.index === 1
则 b节点需要向右移动
===第二轮遍历结束===

最终acd 3个节点都没有移动，b节点被标记为移动