React Diff 算法的源码应该怎么读

科技   2024-12-05 11:56   江苏  

这两个月时间密集型的辅导了我的几个学生通过大厂面试,由于面试强度非常高,因此在准备面试时,就对原理这一块的深度有非常大的要求,不能仅仅停留在八股文的层面去糊弄面试官,回答的东西要禁得起拷打。

于是我就专门又重新花了一点时间去读了一下 React 19 的源码。在读的过程中又有了一些新的体会。

这篇文章准备给大家分享一个面试中比较容易被深入探讨到的点:diff 算法。如果你的薪资诉求非常高,在 30 K 以上,那么对于这一块的理解,就不是随便在网上找一篇文章学一下背一下就能达到要求的了。就要求我们自己有能力去源码中寻找答案。这篇文章主要是为了帮助大家梳理 diff 算法在源码中的实现思路、位置,然后让我们自己就有能力去总结出自己的独特理解。

一、函数缓存优化

在前端开发中,有一种比较常用的优化方式。当我们执行一个函数所需要消耗的时间偏长时,第二次执行时,我们可以读取上一次的执行结果,从而跳过运算过程,直接输出结果。

思路大概如下,首先我们定义一个用于缓存的对象

const cache = {
  preA: null,
  preB: null,
  preResult: null
}

这里我们假设 expensive(a, b) 需要花费很长时间,我们要尽量避免重复运算它。

function cul(a, b{
  return expensive(a, b)
}

于是,我们在第二次执行 cal 时,就需要提前判断入参。如果我们发现,两次的执行入参是一样的,那么我们就可以不必重新运算,而是直接返回上一次的运算结果

代码调整如下

function cul(a, b{
  // 对比之后选择复用缓存的结果
  if (cache.preA === a && cache.preB === b) {
    return cache.preResult
  }
  // 缓存参数与结果
  cache.preA = a
  cache.preB = b
  const result = expensive(a, b)
  cache.preResult = result
  return result
}

那么,当我们多次执行如下代码的时候,耗时运算 expensive() 仅会执行一次

cul(1000999)
cul(1000999)
cul(1000999)
cul(1000999)
cul(1000999)

React 的底层更新机制与这个简化版的优化策略一模一样。只不过 React 遇到的需要缓存的内容稍微复杂一点,他的数据结果从一个普通的 cache 对象,变成了一个完整的 Fiber 链表。

二、Fiber 链表结构

我们常说的 Fiber 对象就是 React 中,用以存储入参和返回结果的缓存对象。这里需要注意的是,和虚拟 DOM 不同,Fiber 是一种运行时上下文,他的字段中记录了大量节点在运行过程中的状态。

function FiberNode(tag: WorkTag, pendingProps: mixed, key: null | string, mode: TypeOfMode{
  // 静态数据结构
  this.tag = tag;
  this.key = key;
  this.elementType = null;
  this.type = null;
  this.stateNode = null// 指向真实 DOM 对象

  // 构建 Fiber 树的指针
  this.return = null;
  this.child = null;
  this.sibling = null;
  this.index = 0;

  this.ref = null;

  // 存储更新与状态
  this.pendingProps = pendingProps;
  this.memoizedProps = null;
  this.updateQueue = null;
  this.memoizedState = null;
  this.dependencies = null;
  this.mode = mode;

  // 存储副作用回调
  this.effectTag = NoEffect;
  this.nextEffect = null;
  this.firstEffect = null;
  this.lastEffect = null;

  // 优先级
  this.lanes = NoLanes;
  this.childLanes = NoLanes;

  // 复用节点
  this.alternate = null;
}

其中,如下几个字段,是构成 Fiber 链表的重要字段

// 构建 Fiber 树的指针
this.return = null;
this.child = null;
this.sibling = null;

其中,this.return 指向父节点。

this.child 指向子元素的第一个节点。

this.sibling 指向兄弟节点。

三、深度有限遍历

在代码中,我们的完整应用整合起来大概长这样

<App>
  <Header />
  <Sider />
  <Content />
  <Footer />
</App>

当然,这只是语法糖,实际上他的代码是这样运行的

function App({
  return (
    <>
      {Header()}
      {Sider()}
      {Content()}
      {Footer()}
    </>

  )
}

因此,节点的执行过程,实际上就是一个函数的正常执行过程。他需要满足函数调用栈的执行顺序。也就是深度优先

四、更新机制

React 的每一次更新,都是全量更新。因此,他的执行,都是从最顶层的根节点开始往下执行。这也是 React 被普遍认为性能差的核心原因。

但是实际上,充分利用好 React 的 diff 规则,是可以写出元素级别的细粒度更新的高性能代码的。只是这对开发者的要求非常高,很少有开发者能够充分理解并运用 diff 规则。

因此,当我们明白了这种更新机制之后,在源码中,就很容易找到每一次更新的起点位置。

五、diff 起点

每一次的更新,都是从根节点开始,该位置在 ReactFiberWorkLoop.js

方法名为 performWorkOnRoot

在之前的版本中,并发更新的方法名为 performConcurrentWorkOnRoot,同步更新的方法名为 performSyncWorkOnRoot

export function performWorkOnRoot(
  root: FiberRoot,
  lanes: Lanes,
  forceSync: boolean,
): void 
{
  const shouldTimeSlice =
    !forceSync &&
    !includesBlockingLane(lanes) &&
    !includesExpiredLane(root, lanes);
    
  let exitStatus = shouldTimeSlice
    ? renderRootConcurrent(root, lanes)
    : renderRootSync(root, lanes);
  ...
  ensureRootIsScheduled(root);
}

其中,renderRootConcurrent 会启动 workLoopConcurrent 循环,

renderRootSync,该方法会启动 workLoopSync 循环,

// The fiber we're working on
let workInProgress: Fiber | null = null;

// workInProgress 起始值为根节点
const rootWorkInProgress = createWorkInProgress(root.current, null);
workInProgress = rootWorkInProgress;
/** @noinline */
function workLoopConcurrent({
  // Perform work until Scheduler asks us to yield
  while (workInProgress !== null && !shouldYield()) {
    // $FlowFixMe[incompatible-call] found when upgrading Flow
    performUnitOfWork(workInProgress);
  }
}

workLoopSync 的逻辑非常简单,就是开始对 Fiber 节点进行遍历。

// The work loop is an extremely hot path. Tell Closure not to inline it.
/** @noinline */
function workLoopSync({
  // Perform work without checking if we need to yield between fiber.
  while (workInProgress !== null) {
    performUnitOfWork(workInProgress);
  }
}

他们的差别就是是否支持在循环过程中,被 shouldYield() 中断循环的执行。最终他们都会执行 performUnitOfWork

这里很核心的一个知识点就是,workInProgress 是一个全局上下文变量,他的值会在执行的过程中不断发生变化。许多人会因为许多文章中提到的双缓存机制对该变量产生误解。实际上,他指的是当前正在被比较的节点。而不仅仅只是 Fiber 树的起点。我们会在后续的分析中,看到他不停的被改变,然后执行下一个节点

从逻辑中我们可以得出结论,当最终没有节点时,workInProgress = null,循环才会结束。

我们注意关注接下来的 performUnitOfWork 方法

function performUnitOfWork(unitOfWork: Fiber): void {
  const current = unitOfWork.alternate;
  setCurrentDebugFiberInDEV(unitOfWork);

  let next;
  if (enableProfilerTimer && (unitOfWork.mode & ProfileMode) !== NoMode) {
    startProfilerTimer(unitOfWork);
    next = beginWork(current, unitOfWork, subtreeRenderLanes);
    stopProfilerTimerIfRunningAndRecordDelta(unitOfWork, true);
  } else {
    next = beginWork(current, unitOfWork, subtreeRenderLanes);
  }

  resetCurrentDebugFiberInDEV();
  unitOfWork.memoizedProps = unitOfWork.pendingProps;
  if (next === null) {
    // If this doesn't spawn new work, complete the current work.
    completeUnitOfWork(unitOfWork);
  } else {
    workInProgress = next;
  }

  ReactCurrentOwner.current = null;
}

我们要把 currentworkInProgress 理解成为一个一直会移动的指针,他们总是指向当前正在执行的 Fiber 节点。当前节点执行完之后,我们就会在修改 workInProgress 的值

核心的代码是下面这两句

next = beginWork(current, unitOfWork, subtreeRenderLanes);
workInProgress = next;

其中,current 表示已经上一次缓存的 Fiber 节点,workInProgress 表示当前构建的 Fiber 节点。

了解这个循环过程,是关键。希望我这样解释之后,大家都能够完整的理解到我想要传达的含义。

六、beginWork 的作用

这里需要特别注意的是,beginWork 是利用当前节点,去计算下一个节点。因此我们要特别关注他的入参和返回值。才能够更加准确的理解 diff 的原理。

next = beginWork(current, unitOfWork, subtreeRenderLanes);

在 beginWork 的执行中,会优先比较当前节点的 props 与 context,来决定是否需要复用下一个节点。注意理解这句话,可能跟我们常规的理念很不一样。这也是准确理解 React diff 的关键。

我们会在后续的代码中观察这一逻辑。现在先来看一下 beginWork 中的代码和比较逻辑。

function beginWork(
  current: Fiber | null,
  workInProgress: Fiber,
  renderLanes: Lanes,
): Fiber | null 
{
  if (current !== null) {
    const oldProps = current.memoizedProps;
    const newProps = workInProgress.pendingProps;

    if (
      oldProps !== newProps ||
      hasLegacyContextChanged() ||
      // Force a re-render if the implementation changed due to hot reload:
      (__DEV__ ? workInProgress.type !== current.type : false)
    ) {
      // If props or context changed, mark the fiber as having performed work.
      // This may be unset if the props are determined to be equal later (memo).
      didReceiveUpdate = true;
    } else {
      // Neither props nor legacy context changes. Check if there's a pending
      // update or context change.
      const hasScheduledUpdateOrContext = checkScheduledUpdateOrContext(
        current,
        renderLanes,
      );
      if (
        !hasScheduledUpdateOrContext &&
        // If this is the second pass of an error or suspense boundary, there
        // may not be work scheduled on `current`, so we check for this flag.
        (workInProgress.flags & DidCapture) === NoFlags
      ) {
        // No pending updates or context. Bail out now.
        didReceiveUpdate = false;
        return attemptEarlyBailoutIfNoScheduledUpdate(
          current,
          workInProgress,
          renderLanes,
        );
      }
      ...

这里的关键是一个名为 didReceiveUpdate 的全局上下文变量。该变量用于标记当前 fiber 节点是否需要复用其子 fiber 节点。

其中 props 与 context 的比较代码如下

if (
  oldProps !== newProps ||
  hasLegacyContextChanged() ||
  // Force a re-render if the implementation changed due to hot reload:
  (__DEV__ ? workInProgress.type !== current.type : false)
) {
  ...
}

然后这里还有一个关键比较函数  checkScheduledUpdateOrContext,该函数用于比较是否存在 update 与 context 的变化。

function checkScheduledUpdateOrContext(
  current: Fiber,
  renderLanes: Lanes,
): boolean 
{
  // Before performing an early bailout, we must check if there are pending
  // updates or context.
  const updateLanes = current.lanes;
  if (includesSomeLane(updateLanes, renderLanes)) {
    return true;
  }
  // No pending update, but because context is propagated lazily, we need
  // to check for a context change before we bail out.
  if (enableLazyContextPropagation) {
    const dependencies = current.dependencies;
    if (dependencies !== null && checkIfContextChanged(dependencies)) {
      return true;
    }
  }
  return false;
}

这里很难理解的地方在于 state 的比较是如何发生的。简单说一下,当我们在刚开始调用 dispatchReducerAction 等函数触发更新时,都会提前给被影响的 fiber 节点标记更新优先级。然后再通过 scheduleUpdateOnFiber 进入后续的调度更新流程。

例如这样

function dispatchReducerAction<SA>(
  fiber: Fiber,
  queue: UpdateQueue<S, A>,
  action: A,
): void 
{
  ...
  const lane = requestUpdateLane(fiber);
  ...
  scheduleUpdateOnFiber(root, fiber, lane);

因此,我们可以通过 includesSomeLane 方法来比较前后两次 fiber 节点的优先级是否发生了变化来判断是否存在更新。

didReceiveUpdate 的值的变化非常重要,除了在 beginWork 执行的时候,我们比较了 props 和 context 之外,在前置的逻辑中,还设定一个了一个方法用于设置他的值为 true。

export function markWorkInProgressReceivedUpdate({
  didReceiveUpdate = true;
}

该方法被运用在 state 的比较结果中

function updateReducer<SIA>(
  reducer: (S, A) => S,
  initialArg: I,
  init?: I => S,
): [SDispatch<A>] 
{
  const hook = updateWorkInProgressHook();
  return updateReducerImpl(hook, ((currentHook: any): Hook), reducer);
}

function updateReducerImpl<SA>(
  hook: Hook,
  current: Hook,
  reducer: (S, A) => S,
): [SDispatch<A>] 
{
  const queue = hook.queue;
  ...
  // Mark that the fiber performed work, but only if the new state is
  // different from the current state.
  if (!is(newState, hook.memoizedState)) {
    markWorkInProgressReceivedUpdate();
  }
  ...
}

当 state、props、context 的比较结果都没有发生变化时,表示此时没有更新发生,因此会直接进入 bailout。

// No pending updates or context. Bail out now.
didReceiveUpdate = false;
return attemptEarlyBailoutIfNoScheduledUpdate(
  current,
  workInProgress,
  renderLanes,
);

后续调用的方法为 bailoutOnAlreadyFinishedWork,会返回当前节点的子节点进行复用,重点关注下面的代码。

function bailoutOnAlreadyFinishedWork(
  current: Fiber | null,
  workInProgress: Fiber,
  renderLanes: Lanes,
): Fiber | null 
{
  ...
  // This fiber doesn't have work, but its subtree does. Clone the child
  // fibers and continue.
  cloneChildFibers(current, workInProgress);
  return workInProgress.child;
}

如果比较结果是无法复用,那么就会根据不同的 tag 执行不同的创建函数

switch (workInProgress.tag) {
  case LazyComponent: {
    const elementType = workInProgress.elementType;
    return mountLazyComponent(
      current,
      workInProgress,
      elementType,
      renderLanes,
    );
  }
  case FunctionComponent: {
    const Component = workInProgress.type;
    const unresolvedProps = workInProgress.pendingProps;
    const resolvedProps =
      disableDefaultPropsExceptForClasses ||
      workInProgress.elementType === Component
        ? unresolvedProps
        : resolveDefaultPropsOnNonClassComponent(Component, unresolvedProps);
    return updateFunctionComponent(
      current,
      workInProgress,
      Component,
      resolvedProps,
      renderLanes,
    );
  }
  case ClassComponent: {
    const Component = workInProgress.type;
    const unresolvedProps = workInProgress.pendingProps;
    const resolvedProps = resolveClassComponentProps(
      Component,
      unresolvedProps,
      workInProgress.elementType === Component,
    );
    return updateClassComponent(
      current,
      workInProgress,
      Component,
      resolvedProps,
      renderLanes,
    );
  }
  ...
}

我们重点关注 updateFunctionComponent,并重点关注如下几行代码

function updateFunctionComponent(
  current: null | Fiber,
  workInProgress: Fiber,
  Component: any,
  nextProps: any,
  renderLanes: Lanes,
{
  ...
  reconcileChildren(current, workInProgress, nextChildren, renderLanes);
  return workInProgress.child;
}

reconcileChildren 中会调用 reconcileChildFibers 方法,该方法则可以被称为是子节点 diff 的入口函数。他会根据 newChild 的不同类型做不同的处理。

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;
    }

    // Handle object types
    if (typeof newChild === 'object' && newChild !== null) {
      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:
          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 (isArray(newChild)) {
        return reconcileChildrenArray(
          returnFiber,
          currentFirstChild,
          newChild,
          lanes,
        );
      }

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

      throwOnInvalidObjectType(returnFiber, newChild);
    }

    if (
      (typeof newChild === 'string' && newChild !== '') ||
      typeof newChild === 'number'
    ) {
      return placeSingleChild(
        reconcileSingleTextNode(
          returnFiber,
          currentFirstChild,
          '' + newChild,
          lanes,
        ),
      );
    }

    if (__DEV__) {
      if (typeof newChild === 'function') {
        warnOnFunctionType(returnFiber);
      }
    }

    // Remaining cases are all treated as empty.
    return deleteRemainingChildren(returnFiber, currentFirstChild);
  }

  return reconcileChildFibers;
}

子节点的类型非常多,每一种类型如何处理我们都要单独去判断。我们这里以其中一个单元素节点为例 reconcileSingleElement 来继续分析。他的代码如下

function reconcileSingleElement(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  element: ReactElement,
  lanes: Lanes,
): Fiber 
{
  const key = element.key;
  let child = currentFirstChild;
  while (child !== null) {
    // TODO: If key === null and child.key === null, then this only applies to
    // the first item in the list.
    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;
          if (__DEV__) {
            existing._debugSource = element._source;
            existing._debugOwner = element._owner;
          }
          return existing;
        }
      } else {
        if (
          child.elementType === elementType ||
          // Keep this check inline so it only runs on the false path:
          (__DEV__
            ? isCompatibleFamilyForHotReloading(child, element)
            : false) ||
          // Lazy types should reconcile their resolved type.
          // We need to do this after the Hot Reloading check above,
          // because hot reloading has different semantics than prod because
          // it doesn't resuspend. So we can't let the call below suspend.
          (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;
          if (__DEV__) {
            existing._debugSource = element._source;
            existing._debugOwner = element._owner;
          }
          return existing;
        }
      }
      // Didn't match.
      deleteRemainingChildren(returnFiber, child);
      break;
    } else {
      deleteChild(returnFiber, child);
    }
    child = child.sibling;
  }

  if (element.type === REACT_FRAGMENT_TYPE) {
    const created = createFiberFromFragment(
      element.props.children,
      returnFiber.mode,
      lanes,
      element.key,
    );
    created.return = returnFiber;
    return created;
  } else {
    const created = createFiberFromElement(element, returnFiber.mode, lanes);
    created.ref = coerceRef(returnFiber, currentFirstChild, element);
    created.return = returnFiber;
    return created;
  }
}

在代码中我们可以看到,这里会以此比较 key、type、tag 的值。如果都相同,则选择复用,返回已经存在的节点

const existing = useFiber(child, element.props.children);
existing.return = returnFiber;
return existing;

到这里,diff 的整个流程都已经比较清楚了。在理解 diff 时,我们对 Fiber 的链表结构足够清晰,明确两个指针 currentworkInProgress 的含义与移动方向,理解起来就会非常容易。

七、总结

由于时间有限,文字的表达能力有限,本文并没有完全的从结论的角度为大家介绍 diff 算法是如何如何。而是从源码的角度引导大家应该如何在代码中去自己提炼相关的观点。因此,主要的表诉方式是以大概的实现思路加上源码的函数调用路径来跟大家分享。

其中涉及到的需要自己去扩展的细节和结论还比较多。但是在本文的框架之下,我们在读源码的时候,就有了自己去提炼更准确知识点的可能性。而不是网上到处找二手资料最终也没太搞懂。

后续我们要扩展的是,学会利用这样的 diff 规则,写出总能精准命中缓存的代码,当有状态更新时,只把损耗限制在比较的过程中,从而达到精准的元素级别细粒度更新,让项目性能达到最佳状态。这确实有非常大的难度,我在前面的文章中有跟大家分享具体的细节和方法,大家可以回过头去找找之前的性能优化相关的文章。

最近在写 Next.js 的付费专栏,然后我发现如果我们无法做到完整的利用 diff 规则,那么也很难把 Next.js 利用好。因为 Next.js 要单独把服务端组件拆分出来,所运用的逻辑刚好与利用 diff 规则的思路是完全一样的。我们要通过合理的解耦方式,把服务端组件和客户端组件单独拆开,其中服务端组件所代表的,就是不再二次更新的代码,而客户端组件所代表的,就是最终要更新的组件。

这是一脉相承的思路。当然,也是部分人觉得 Next.js 用起来很难受的原因。如果我们这套思路没有培养成熟的话,我们很难把逻辑完整的解耦开,最坏的结果就是,你的项目中 use client 会无处不在。





  • 我是 ssh,工作 6 年+,阿里云、字节跳动 Web infra 一线拼杀出来的资深前端工程师 + 面试官,非常熟悉大厂的面试套路,Vue、React 以及前端工程化领域深入浅出的文章帮助无数人进入了大厂。
  • 欢迎长按图片加 ssh 为好友,我会第一时间和你分享前端行业趋势,学习途径等等。2024 陪你一起度过!


  • 关注公众号,发送消息:
    指南获取高级前端、算法学习路线,是我自己一路走来的实践。
    简历获取大厂简历编写指南,是我看了上百份简历后总结的心血。
    面经获取大厂面试题,集结社区优质面经,助你攀登高峰
因为微信公众号修改规则,如果不标星或点在看,你可能会收不到我公众号文章的推送,请大家将本公众号星标,看完文章后记得点下赞或者在看,谢谢各位!

前端从进阶到入院
我是 ssh,只想用最简单的方式把原理讲明白。wx:sshsunlight,分享前端的前沿趋势和一些有趣的事情。
 最新文章