❌

阅读视图

发现新文章，点击刷新页面。

🔥🔥🔥 React18 源码学习 - DIFF算法

✇掘金 前端
yyyao

前言

本文的React代码版本为18.2.0

可调试的代码仓库为：GitHub - yyyao-hh/react-debug at master-pure

在React的世界里，每次状态更新都会触发组件的重新渲染。如果直接销毁旧DOM节点并创建新节点，性能开销将无法承受。React通过调和（Reconciliation） 过程，配合DIFF算法，找出需要更新的最小节点集合，实现了高效的UI更新。

本文将带你深React18源码，揭示DIFF算法的核心原理、实现细节和优化策略。

DIFF 算法的策略

策略一：同级比较

React只会对同一层级的节点进行比较，不会跨层级追踪节点变化。

策略二：类型不同则销毁重建

如果节点类型改变，React会直接销毁整个子树，重新构建新的节点。

策略三：Key 值优化列表更新

React使用key来匹配原有树上的子元素，匹配成功就会进行复用。通过key标识节点的稳定性，React可以更准确地识别节点的移动、添加和删除，使得树的转换效率得以提高。

比如：两个同级兄弟节点位置进行了调换，存在key的情况下两个节点都会被复用，而不是卸载重新构建。

DIFF 算法的入口

在上一节我们讲构建Fiber树的时候，讲到了beginWork方法内部主要是根据tag分发逻辑，处理不同类型的Fiber节点。将处理方法的返回的子节点作为下一个遍历节点

/* packages/react-reconciler/src/ReactFiberBeginWork.old.js */

function beginWork(
  current: Fiber | null,
  workInProgress: Fiber,
  renderLanes: Lanes,
): Fiber | null {
  if(...) {...}; // 满足一定条件下执行熔断策略

  switch (workInProgress.tag) {
    case IndeterminateComponent: return mountIndeterminateComponent(...);
    case LazyComponent: return mountLazyComponent(...);
    case FunctionComponent: return updateFunctionComponent(...);
    case ClassComponent: return updateClassComponent(...);
    case HostRoot: return updateHostRoot(...);
    case HostComponent: return updateHostComponent(...);
    case HostText: return updateHostText(...);
    case SuspenseComponent: return updateSuspenseComponent(...);
    case HostPortal: return updatePortalComponent(...);
    case ForwardRef: return updateForwardRef(...);
    case Fragment: return updateFragment(...);
    case Mode: return updateMode(...);
    case Profiler: return updateProfiler(...);
    case ContextProvider: return updateContextProvider(...);
    case ContextConsumer: return updateContextConsumer(...);
    case MemoComponent: return updateMemoComponent(...);
    case SimpleMemoComponent: return updateSimpleMemoComponent(...);
    case IncompleteClassComponent: return mountIncompleteClassComponent(...);
    case SuspenseListComponent: return updateSuspenseListComponent(...);
    case ScopeComponent: return updateScopeComponent(...);
    case OffscreenComponent: return updateOffscreenComponent(...);
    case LegacyHiddenComponent: return updateLegacyHiddenComponent(...);
    case CacheComponent: return updateCacheComponent(...);
    case TracingMarkerComponent: return updateTracingMarkerComponent(...);
  }
}

这些不同的处理逻辑最终都会走到reconcileChildren函数中去处理，这里简单以类组件（ClassComponent）和函数式组件（FunctionComponent）的举例：

// 类组件 (ClassComponent)
function updateClassComponent(...) {
  const nextUnitOfWork = finishClassComponent(...);
  
  return nextUnitOfWork;
}

function finishClassComponent(...) {
  reconcileChildren(current, workInProgress, nextChildren, renderLanes);

  return workInProgress.child;
}

// 函数式组件 (FunctionComponent)
function updateFunctionComponent(...) {
  reconcileChildren(current, workInProgress, nextChildren, renderLanes);
  
  return workInProgress.child;
}

/* src/react/packages/react-reconciler/src/ReactFiberBeginWork.old.js */

export function reconcileChildren(...) {
  if (current === null) {
    workInProgress.child = mountChildFibers(...);
  } else {
    workInProgress.child = reconcileChildFibers(...);
  }
}

/* src/react/packages/react-reconciler/src/ReactChildFiber.old.js */

export const reconcileChildFibers = ChildReconciler(true);
export const mountChildFibers = ChildReconciler(false);

/* src/react/packages/react-reconciler/src/ReactChildFiber.old.js */

function ChildReconciler(shouldTrackSideEffects) {

  ...

  function reconcileChildFibers() {}

  return reconcileChildFibers;
}

所以reconcileChildFibers函数是实现Diff算法的核心方法

DIFF 算法的实现

我们紧接着入口之后，来分析reconcileChildFibers函数的内部逻辑。

  1. 首先处理顶级且无key的Fragment元素，满足条件则直接使用它的孩子。这里值得注意的两点：

    a. 存在key的Fragment不满足条件，于是乎在下方“处理单元素”逻辑中又会处理一下。

    b. 非顶级的Fragment依旧不满足条件，在下方“处理数组元素”的逻辑中会进行处理。

  2. 如果是一个对象，那么它是一个ReactElement。分为普通元素、Lazy组件、Portal组件、节点数组、可迭代对象分别进行处理；

  3. 如果是string或number类型，调用处理文本节点的方法。

  4. 剩余情况：可能为null、undefined、false或''，不能转化为Fiber节点，因此直接删除所有旧子Fiber节点。

function reconcileChildFibers(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChild: any,
  lanes: Lanes,
): Fiber | null {
  
  /* 1. 顶级无key的Fragment元素, 直接使用它的children */
  const isUnkeyedTopLevelFragment =
    typeof newChild === 'object' &&
    newChild !== null &&
    newChild.type === REACT_FRAGMENT_TYPE &&
    newChild.key === null;
  if (isUnkeyedTopLevelFragment) {
    newChild = newChild.props.children;
  }

  /* 2. 处理对象类型 */
  if (typeof newChild === 'object' && newChild !== null) {
    switch (newChild.$$typeof) {
      // 2.1 React 元素
      case REACT_ELEMENT_TYPE:
        return placeSingleChild(
          reconcileSingleElement(
            returnFiber,
            currentFirstChild,
            newChild,
            lanes,
          ),
        );
      // 2.2 Portal
      case REACT_PORTAL_TYPE:
        return placeSingleChild(
          reconcileSinglePortal(
            returnFiber,
            currentFirstChild,
            newChild,
            lanes,
          ),
        );
      // 2.3 懒加载组件
      case REACT_LAZY_TYPE:
        const payload = newChild._payload;
        const init = newChild._init;
        return reconcileChildFibers(
          returnFiber,
          currentFirstChild,
          init(payload),
          lanes,
        );
    }

    // 2.4. 数组类型处理
    if (isArray(newChild)) {
      return reconcileChildrenArray(
        returnFiber,
        currentFirstChild,
        newChild,
        lanes,
      );
    }

    // 2.5 可迭代对象处理
    if (getIteratorFn(newChild)) {
      return reconcileChildrenIterator(
        returnFiber,
        currentFirstChild,
        newChild,
        lanes,
      );
    }

    // 2.6 无效对象类型错误
    throwOnInvalidObjectType(returnFiber, newChild);
  }

  /* 3. 处理文本节点类型 */
  if (
    (typeof newChild === 'string' && newChild !== '') ||
    typeof newChild === 'number'
  ) {
    return placeSingleChild(
      reconcileSingleTextNode(
        returnFiber,
        currentFirstChild,
        '' + newChild,
        lanes,
      ),
    );
  }

  /* 4. 剩余情况 */
  return deleteRemainingChildren(returnFiber, currentFirstChild);
}

处理单节点

reconcileSingleElement方法用于处理当新的子节点是一个单独的元素（不是数组或文本节点）时的情况。

它的处理分为两个阶段，判断条件便是child !== null

  1. 更新阶段（while循环）
  2. 初始化阶段或在循环中不满足复用条件（while循环之后）

首先while循环的逻辑：遍历旧子Fiber节点，尝试找到可以复用的Fiber节点：

  • 如果key相同且type相同，则复用并删除其他兄弟节点；
  • 如果key相同但type不同，则删除包括当前节点在内的所有子节点，然后跳出循环；
  • 如果key不同，则标记当前child为删除，继续遍历下一个兄弟节点。

然后是循环之后的逻辑：遍历完或break后未找到可复用节点，直接创建新的Fiber节点。

function reconcileSingleElement(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  element: ReactElement,
  lanes: Lanes,
): Fiber {
  const key = element.key;
  let child = currentFirstChild;
  /**
   * 1. 更新阶段
   * - 如果key相同且type相同, 则复用并删除其他兄弟节点
   * - 如果key相同但type不同, 则删除包括当前节点在内的所有子节点, 然后跳出循环
   * - 如果key不同, 则标记当前child为删除, 继续遍历下一个兄弟节点
   */
  while (child !== null) {
    if (child.key === key) {
      const elementType = element.type;
      if (elementType === REACT_FRAGMENT_TYPE) {
        if (child.tag === Fragment) {
          deleteRemainingChildren(returnFiber, child.sibling);
          const existing = useFiber(child, element.props.children);
          existing.return = returnFiber;
          return existing;
        }
      } else {
        if (
          child.elementType === elementType ||
          (__DEV__
            ? isCompatibleFamilyForHotReloading(child, element)
            : false) ||
          (typeof elementType === 'object' &&
            elementType !== null &&
            elementType.$$typeof === REACT_LAZY_TYPE &&
            resolveLazy(elementType) === child.type)
        ) {
          deleteRemainingChildren(returnFiber, child.sibling);
          const existing = useFiber(child, element.props);
          existing.ref = coerceRef(returnFiber, child, element);
          existing.return = returnFiber;
          return existing;
        }
      }
      // key相同, 类型不同, 删除该节点和其兄弟节点
      deleteRemainingChildren(returnFiber, child);
      break;
    } else {
      // 如果key不同, 则标记当前child为删除, 继续遍历下一个兄弟节点
      deleteChild(returnFiber, child);
    }
    child = child.sibling;
  }

  /**
   * 2. 初始化阶段 ｜ 或循环中不满足复用条件, 直接创建新的Fiber节点
   */
  if (element.type === REACT_FRAGMENT_TYPE) { // Fragment 组件
    const created = createFiberFromFragment(
      element.props.children,
      returnFiber.mode,
      lanes,
      element.key,
    );
    created.return = returnFiber;
    return created;
  } else { // 原生DOM元素、函数组件、类组件等
    const created = createFiberFromElement(element, returnFiber.mode, lanes);
    created.ref = coerceRef(returnFiber, currentFirstChild, element);
    created.return = returnFiber;
    return created;
  }
}

总结下reconcileSingleElement方法的作用：负责处理单个React元素的更新，它的目标：

  1. 在现有子节点链表中找到可以复用的节点
  2. 删除不需要的旧节点（打标记，commit阶段处理）
  3. 创建新的Fiber节点（如果没有可复用的）

处理多节点

reconcileChildrenArray函数负责协调一个数组类型的子元素列表。

  1. 第一次循环：同时遍历旧的子Fiber节点链表和新的子元素数组，直到其中一个遍历完。
    在遍历中，通过updateSlot函数尝试复用旧节点（key相同则复用，否则返回null）。
    1. 如果复用失败（key不同），则跳出循环。
    2. 如果复用成功，但是位置可能发生变化，则通过placeChild标记位置（是否需要移动）。
  1. 如果新子元素数组遍历完（newIdx === newChildren.length），说明剩下的旧节点都是多余，需要删除。
  2. 如果旧节点链表遍历完（oldFiber === null），说明剩下的新子元素都是需要新增的，直接循环创建新的Fiber节点。
  3. 如果以上都不是，说明有节点位置发生变化（比如中间插入了新节点，或者节点被删除导致旧节点有剩余），此时将剩余的旧节点放入一个Map中（key作为索引，如果没有key则用index），然后继续遍历新子元素数组，从Map中查找可复用的节点，并标记移动。
  4. 最后，如果还有旧节点未被复用，则标记删除。
function reconcileChildrenArray(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChildren: Array<*>,
  lanes: Lanes,
): Fiber | null {
  let resultingFirstChild: Fiber | null = null; // 结果链表的头节点
  let previousNewFiber: Fiber | null = null;    // 上一个创建的Fiber

  let oldFiber = currentFirstChild; // 旧Fiber链表的节点, 开始指向同层的第一个节点
  let lastPlacedIndex = 0;          // 已经处理完的节点中，最后一个"不需要移动"的节点在旧列表中的位置
  let newIdx = 0;                   // 新children数组的当前索引
  let nextOldFiber = null;          // 下一个要处理的旧Fiber（临时存储）
  /**
   * 1. 同时遍历旧的子Fiber节点链表和新的子元素数组, 直到其中一个遍历完
   */
  for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
    if (oldFiber.index > newIdx) {
      nextOldFiber = oldFiber;
      oldFiber = null;
    } else {
      nextOldFiber = oldFiber.sibling;
    }
    // updateSlot: 尝试复用旧节点（key相同则复用，否则返回null）
    const newFiber = updateSlot(
      returnFiber,
      oldFiber,
      newChildren[newIdx],
      lanes,
    );
    // 匹配失败, 不能复用
    if (newFiber === null) {
      if (oldFiber === null) {
        oldFiber = nextOldFiber;
      }
      break;
    }
    if (shouldTrackSideEffects) {
      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;
  }

  /**
   * 2. 如果新子元素数组遍历完, 说明剩下的旧节点都是多余, 需要删除
   */
  if (newIdx === newChildren.length) {
    deleteRemainingChildren(returnFiber, oldFiber);
    return resultingFirstChild;
  }

  /**
   * 3. 如果旧节点链表遍历完, 说明剩下的新子元素都是需要新增的, 直接循环创建
   */
  if (oldFiber === null) {
    for (; newIdx < newChildren.length; newIdx++) {
      const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
      if (newFiber === null) {
        continue;
      }
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
    }
    return resultingFirstChild;
  }

  /**
   * 4. 如果以上都不是, 说明有节点位置发生变化, 此时将剩余的旧节点放入一个Map中,
   * 然后继续遍历新子元素数组, 从Map中查找可复用的节点, 并标记移动
   */
  const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
  for (; newIdx < newChildren.length; newIdx++) {
    const newFiber = updateFromMap(
      existingChildren,
      returnFiber,
      newIdx,
      newChildren[newIdx],
      lanes,
    );
    if (newFiber !== null) {
      if (shouldTrackSideEffects) {
        if (newFiber.alternate !== null) {
          existingChildren.delete(
            newFiber.key === null ? newIdx : newFiber.key,
          );
        }
      }
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
    }
  }

  /**
   * 5. 最后, 如果还有旧节点未被复用, 则标记删除
   */
  if (shouldTrackSideEffects) {
    existingChildren.forEach(child => deleteChild(returnFiber, child));
  }

  return resultingFirstChild;
}

总结下reconcileChildrenArray方法的作用：负责协调一个数组类型的子元素列表，它的设计：

第一阶段：顺序比较（处理相同位置节点）

↓

第二阶段：处理新增/删除边界

↓

第三阶段：Map查找（处理节点移动）

实际案例：列表重排的DIFF过程

假设有如下列表更新：

// 更新前
<ul>
  <li key="A">A</li>
  <li key="B">B</li>
  <li key="C">C</li>
  <li key="D">D</li>
</ul>

// 更新后(D移动到B之前)
<ul>
  <li key="A">A</li>
  <li key="D">D</li>
  <li key="B">B</li>
  <li key="C">C</li>
</ul>

DIFF过程：

  1. 第一轮遍历：比较A-A（复用），比较B-D（key不同，跳出第一轮）
  2. 建立Map：{B: B_Fiber, C: C_Fiber, D: D_Fiber}
  3. 第二轮遍历：
    • 处理D：从Map中找到D_Fiber，lastPlacedIndex=0，oldIndex=3>0，不需要移动
    • 处理B：从Map中找到B_Fiber，lastPlacedIndex=3，oldIndex=1<3，需要移动
    • 处理C：从Map中找到C_Fiber，lastPlacedIndex=3，oldIndex=2<3，需要移动
  1. 结果：D保持原位，B和C向后移动

总结

React的DIFF算法是一个经过精心设计和不断优化的复杂系统。从React16的Fiber架构到React18的并发特性，DIFF算法始终围绕着以下核心目标：

  1. 高效性：通过O(n)复杂度的算法快速找出差异
  2. 稳定性：确保在可中断渲染中UI的一致性
  3. 可预测性：开发者可以通过key等手段控制更新行为
  4. 渐进增强：支持并发渲染，提高应用响应速度

下一章我们将了解真实DOM的变更：commit阶段

❌