在日常面试中我们可能会经常被问到 React 的 diff 算法，那么通过这篇文章你应该能清楚地知道 diff 算法、虚拟 DOM、是什么以及一整个 React 的执行流程。

在开始之前分享两个我的两个开源项目,它们分别是:

• 前端脚手架 create-neat
• 在线代码协同编辑器

这两个项目都会一直维护的,如果你也喜欢,欢迎 star 🥰🥰🥰

什么是 JSX

JSX 是一种用于在 JavaScript 代码中编写 UI 组件的语法扩展。它的主要特点有以下几个方面:

• 声明性: JSX 使 UI 组件的创建变得更加声明性，因为你可以像编写 HTML 一样编写 UI 结构。
• 组件嵌套: 您可以将多个组件嵌套在一起，以构建复杂的 UI。这使得代码的组织和重用变得更加容易。
• JavaScript 表达式: 您可以在 JSX 中嵌入 JavaScript 表达式，这使得动态生成 UI 内容变得非常方便。只需将表达式包装在大括号 {} 中即可。

在 React 中，JSX 实际上是 React.createElement 的语法糖，在 ReactElement 函数中的主要作用是返回一个对象,并标记为 React Element,具体代码如下：

const ReactElement = function (type, key, ref, self, source, owner, props) {
  const element = {
    // 标记这是个 React Element
    $$typeof: REACT_ELEMENT_TYPE,

    type: type,
    key: key,
    ref: ref,
    props: props,
    _owner: owner,
  };

  return element;
};

以下是返回的对象中的以下解释：

• type：表示元素的类型，可以是 HTML 标签名,如 div、span 等或自定义组件。

• key：表示元素的唯一标识，通常用于优化渲染的过程中，帮助 React 识别元素的更新、新增或删除。

• ref：表示对元素的引用，通常用于访问或操作元素的 DOM 节点。

• props：包含了元素的属性，这是一个对象，包括元素的所有属性和子元素。这个参数是一个对象，其中包含了所有传递给元素的属性。

• _owner：表示拥有当前元素的组件，通常用于 React 内部的一些操作和优化。

• $$typeof：一个特殊的属性，用于标识这是一个 React 元素对象。

在我们的项目中编写如下代码：

import React, { useRef } from "react";

const App = () => {
  const ref = useRef(null);

  return (
    <h1 className="moment" ref={ref}>
      <div key="1" className="title">
        supper
      </div>
      <div key="2" className="content">
        moment
      </div>
    </h1>
  );
};

export default App;

这段代码经过 babel 编译之后最终会变成如下代码结构:

import React, { useRef } from "react";
var App = function App() {
  var ref = useRef(null);
  return /*#__PURE__*/ React.createElement(
    "h1",
    {
      className: "moment",
    },
    /*#__PURE__*/ React.createElement(
      "div",
      {
        key: "1",
        className: "title",
        ref: ref,
      },
      "supper"
    ),
    /*#__PURE__*/ React.createElement(
      "div",
      {
        key: "2",
        className: "content",
      },
      "moment"
    )
  );
};
export default App;

在 React.createElement 函数中,它接收三个参数第一个为 type,div 或者 span 之类的 html 元素的字符串。

createElement 函数的第二个参数 是 config，它用于传递一些配置和特殊属性给 React 元素。这个参数通常是一个对象。创建 React 元素时传递各种配置和特殊属性，以满足组件的不同需求。

而第三个就是当前元素的 children 了。

所以它最终编译成的虚拟 DOM 有如下图所示：

这些东西都和我们上面所讲到的都一一对应起来了。

什么是虚拟 DOM

在我们深入学习虚拟 DOM 的时候，我们就可以理解为什么 React 的 diff 算法变得如此不可或缺。虚拟 DOM 是实际 DOM 的轻量级副本。这个概念是 React 的基石，也是 React 在更新和渲染网页方面如此快速高效的原因。不是直接对真正的 DOM 进行更改(就性能而言，这可能是缓慢和昂贵的)，而是首先对虚拟 DOM 进行更改。

在进行这些更改之后，React diff 算法开始发挥作用。React 中的这个 diff 算法将更新后的 Virtual DOM 与之前的版本进行比较。通过确定将旧的 Virtual DOM 转换为新 DOM 所需的最小操作数，React 确保了最佳性能。一旦确定了特定的更改，React 就只更新真正 DOM 的这些部分，而不是重新更新整个页面。

Fiber 架构

在 React 中，整体的渲染流程分为了两个阶段：

• render 阶段：从虚拟 DOm 转换成 Fiber，并且对需要 DOM 操作的阶段打上 effectTag 的标记。
• commit 阶段：对有 effectTag 标记的 Fiber 节点进行 dom 操作，并执行所有的 effect 副作用。

Fiber 树的构建是深度优先的，它是一个递到归的过程，也就是先向下构建子级 Fiber 节点，子级节点构建完成后，再向上构建父级 Fiber 节点，所以 EffectList 中总是子级 Fiber 节点在前面。

而 commit 阶段是不可中断的，如果在 commit 阶段中断，可能会导致部分 DOM 更新，用户可能会看到界面在多个状态之间闪烁或不稳定。通过确保 commit 阶段不可中断，React 可以在渲染过程中提供更一致的用户体验。

从虚拟 DOM 转成 Fiber 的过程叫做 reconcile（调和），这个过程是可以打断的，由 scheduler 调度执行。

从虚拟 DOM 到 Fiber 的主要步骤有以下几个方面：

1. 虚拟 DOM 构建：就是我们前面的内容中讲到的 JSX 编译的过程。
2. 协调：在协调阶段，React 会比较两棵虚拟 DOM 树：先前渲染的虚拟 DOM 树（之前的状态）和新构建的虚拟 DOM 树（新状态）。React 使用 diff 算法来比较它们之间的差异，以确定需要进行哪些更新操作。
3. 生成 Fiber 树：一旦确定了需要进行的更新操作，React 将这些更新操作表示为 Fiber 节点的树。Fiber 节点是一种用于描述组件渲染状态和副作用的数据结构。每个 Fiber 节点都包含了组件的类型、状态、子节点、兄弟节点等信息，以便 React 可以更好地控制渲染过程和协调。
4. 构建工作单元：React 将要执行的更新操作分解成一系列称为工作单元的任务，也就是 effect list。这些工作单元包括添加、更新或删除组件以及执行副作用等操作。每个工作单元都与一个 Fiber 节点相关联。
5. 执行工作单元：React 使用调度器来管理工作单元的执行顺序。它可以根据任务的优先级和其他因素来决定哪个工作单元应该先执行。React 会逐个执行这些工作单元，更新组件状态并执行副作用。
6. 更新 Fiber 树：在执行工作单元时，React 会根据工作单元的执行结果来更新 Fiber 树。这可能涉及到更改 Fiber 节点的状态、构建新的 Fiber 节点或标记节点为不需要渲染等操作。

diff 算法作用在 reconcile 阶段，也就是构建 JSX 编译转换之后，FIber 树建立之前。

第一次渲染不需要 diff，直接虚拟 DOM 转 FIber。而再次渲染的时候，会产生新的虚拟 DOM，这时候要和之前的 fiber 做下对比，决定怎么产生新的 fiber，对可复用的节点打上修改的标记，剩余的旧节点打上删除标记，新节点打上新增标记。

深入理解 React 的 diff 算法

React 中维护着两棵 fiber 树，一棵是正在展示的 UI 对应的那棵树，我们称为 current 树；另一棵通过更新，将要构建的树。那么在更新的过程中，是通过怎么样的对比过程，来决定是复用之前的节点，还是创建新的节点。

reconcileChildren

函数 reconcileChildren() 是一个入口函数，这里会根据 current 的 fiber 节点的状态，分化为 mountChildFibers 和 reconcileChildFibers，该函数的具体实现如下代码所示：

export function reconcileChildren(
  current: Fiber | null,
  workInProgress: Fiber,
  nextChildren: any,
  renderLanes: Lanes
) {
  if (current === null) {
    /**
     * 第一次渲染不存在 current.child,都是父亲节点先渲染,子节点后渲染
     * 如果此新 fiber 没有旧 fiber,说明此新 fiber 是新创建的
     */
    workInProgress.child = mountChildFibers(
      workInProgress,
      null,
      nextChildren,
      renderLanes
    );
  } else {
    // 如果有老 fiber的话,做 DOM-DIFF 拿老的fiber 和新的 fiber 进行 DOM 比较
    workInProgress.child = reconcileChildFibers(
      workInProgress,
      current.child,
      nextChildren,
      renderLanes
    );
  }
}

我们再来看一下下面这段代码:

export const reconcileChildFibers = ChildReconciler(true); // 需要收集副作用
export const mountChildFibers = ChildReconciler(false); // 不用追踪副作用

从上面代码可以看出， mount 时执行的 reconcileChildFibers 和 update 时执行的 mountChildFibers 方式，实际上都是由 ChildReconciler 这个方法封装出来的，差别只在于传参不同。

ChildReconciler

该函数就只接收一个参数，并且返回的是一个函数，该函数实现大概如下所示：

function ChildReconciler(shouldTrackSideEffects) {
  // ......
  function reconcileChildFibers(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null, // current 树上对应的当前 Fiber 节点的第一个子 Fiber 节点，mount 时为 null，主要是为了是否能复用之前的节点
    newChild: any, // returnFiber中的element结构，用来构建returnFiber的子节点
    lanes: Lanes // 优先级相关
  ): Fiber | null {
    // 省略
    return deleteRemainingChildren(returnFiber, currentFirstChild);
  }

  return reconcileChildFibers;
}

当 current 对应的 fiber 节点为 null 时，那它就没有子节点，也无所谓复用和删除的说法，直接按照 workInProgress 里的 element 构建新的 fiber 节点即可，这时，是不用收集副作用的。

若 current 对应的 fiber 节点不为 null 时，那么就把 current 的子节点拿过来，看看是否有能复用的节点，有能复用的节点就直接复用；不能复用的，比如类型发生了改变的（div 标签变成了 p 标签），新结构里已经没有该 fiber 节点了等等，都是要打上标记，后续在 commit 阶段进行处理。

reconcileChildFibers

函数 reconcileChildFibers() 不做实际的操作，仅是根据 element 的类型，调用不同的方法来处理，相当于一个路由分发。

该函数的具体实现如下代码所示:

function reconcileChildFibers(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChild: any,
  lanes: Lanes
): Fiber | null {
  // 是否是顶层的没有key的fragment组件
  const isUnkeyedTopLevelFragment =
    typeof newChild === "object" &&
    newChild !== null &&
    newChild.type === REACT_FRAGMENT_TYPE &&
    newChild.key === null;

  // 若是顶层的fragment组件，则直接使用其children
  if (isUnkeyedTopLevelFragment) {
    newChild = newChild.props.children;
  }

  if (typeof newChild === "object" && newChild !== null) {
    switch (newChild.$$typeof) {
      case REACT_ELEMENT_TYPE:
        // 一般的React组件，如<App />或<p></p>等
        return placeSingleChild(
          // 调度单体element结构的元素
          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;
        return reconcileChildFibers(
          returnFiber,
          currentFirstChild,
          init(payload),
          lanes
        );
    }

    if (isArray(newChild)) {
      // 若 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
      )
    );
  }

  return deleteRemainingChildren(returnFiber, currentFirstChild);
}

在该函数中，首先会判断 newChild 的类型，来进入到不同逻辑中，主要有以下的类型：

1. 是否是顶层的 Fragment 元素，如在执行 render()时，用的是 fragment 标签或 <> 包裹，则表示该元素顶级的 Fragment 组件，这里直接使用其 children;
2. 如果 newChild 的类型为对象且不为空，则会根据不同的类型进行不同的操作，如下：

• case REACT_ELEMENT_TYPE:
  1. 如果 newChild 的类型是 REACT_ELEMENT_TYPE，表示它是一个一般的 React 元素，例如 <App /> 或 <p></p> 等。
  2. 在这种情况下，函数会调用 reconcileSingleElement 函数来协调更新或创建这个元素的 Fiber 节点，并通过 placeSingleChild 函数包装以确保返回一个单一的子元素。
• case REACT_PORTAL_TYPE:
  1. 如果 newChild 的类型是 REACT_PORTAL_TYPE，表示它是一个 Portal 元素。
  2. 在这种情况下，函数会调用 reconcileSinglePortal 函数来协调更新或创建这个 Portal 的 Fiber 节点，并通过 placeSingleChild 函数包装以确保返回一个单一的子元素。
• case REACT_LAZY_TYPE:
  1. 如果 newChild 的类型是 REACT_LAZY_TYPE，表示它是一个懒加载元素。
  2. 在这种情况下，函数会从 newChild 中获取 payload 和 init，然后调用 init(payload) 来创建懒加载元素的实际元素，并再次调用 reconcileChildFibers 函数来协调更新或创建这个实际元素的 Fiber 节点。

1. 普通数组，每一项都是合法的其他元素，如一个 div 标签下有并列的 span 标签、函数组件<Count />、纯文本等，这些在 jsx 转换过程中，会形成数组；
2. Iterator，跟数组类似，只是遍历方式不同；
3. string 或 number 类型：如 <div>abc</div> 里的 abc 即为字符串类型的文本,外层的 div 节点依然是 html 标签，在 React 中会把 div 标签和 abc 分成两部分进行处理;

reconcileChildFibers()不是递归函数，他只处理 workInProgress 节点里的 element 结构，无论 element 是一个节点，还是一组节点，只会把这一层的节点都进行转换。若 element 中对应的只有一个 fiber 节点，那就返回这个节点，若是一组数据，则会形成一个 fiber 单向链表，然后返回这个链表的头节点。

该函数的整体思想就是复用，能复用之前 fiber 节点的，绝不创建新的 fiber 节点。只不过，之前的 fiber 节点是否可以复用，复用哪个 fiber 节点，情况比较复杂。

创建单个 Fiber 节点 reconcileSingleElement

若 element 中只对应一个元素，且是普通 React 的函数组件、类组件、html 标签等类型，那我们调用 reconcileSingleElement() 来处理。

在更新时，一旦创建/复用了 Fiber 节点，那么就可以把当前 Fiber 节点下的其它 current 子节点（上次 render 时存在的 Fiber 子节点）给标记为删除，方便 commit 阶段删除这些多余的 DOM 节点。

判断是否可以复用之前的节点，复用节点的标准是 key 一样、类型一样，任意一个不一样，都无法复用。

若无法复用之前的节点，那之前的节点也没留着的必要了，则将之前的节点删除，创建一个新的节点。

在 React 中，它是使用的双缓冲 Fiber 树的，一棵是用来显示的，一棵是用来构建的。复用可以通过 current.alternate 指向对应的那个节点，因为在没有任何更新时，两棵 fiber 树是一一对应的。在产生更新后，可能就会存在对应不上的情况，因此才有了下面的各种 diff 对比环节。

函数具体实现代码如下所示：

function reconcileSingleElement(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  element: ReactElement,
  lanes: Lanes
): Fiber {
  // 获取 workInProgress 中的 key
  const key = element.key;
  // 通过 currentFirstChild 获取当前正在对比的 child，它对应的是第一个子 Fiber。
  let child = currentFirstChild;
  while (child !== null) {
    // 比较key值是否有变化，这是复用Fiber节点的先决条件
    // key 为 null 的情况也认为是相等的
    if (child.key === key) {
      const elementType = element.type;

      if (elementType === REACT_FRAGMENT_TYPE) {
        if (child.tag === Fragment) {
          // 已找到可复用的fiber节点，从下一个节点开始全部删除
          deleteRemainingChildren(returnFiber, child.sibling);
          // 该节点是fragment类型，则复用其children
          const existing = useFiber(child, element.props.children);
          // 重置新Fiber节点的return指针，指向当前Fiber节点
          existing.return = returnFiber;
          return existing;
        }
      } else {
        if (
          child.elementType === elementType ||
          // Keep this check inline so it only runs on the false path:
          (__DEV__
            ? isCompatibleFamilyForHotReloading(child, element)
            : false) ||
          (typeof elementType === "object" &&
            elementType !== null &&
            elementType.$$typeof === REACT_LAZY_TYPE &&
            resolveLazy(elementType) === child.type)
        ) {
          // 已找到可复用的fiber节点，从下一个节点开始全部删除
          deleteRemainingChildren(returnFiber, child.sibling);
          // 复用child节点和element.props属性
          const existing = useFiber(child, element.props);
          existing.ref = coerceRef(returnFiber, child, element);
          existing.return = returnFiber;

          return existing;
        }
      }
      // Didn't match.
      deleteRemainingChildren(returnFiber, child);
      break;
    } else {
      deleteChild(returnFiber, child);
    }
    child = child.sibling;
  }

  // 上面的一通循环没找到可以复用的节点，则接下来直接创建一个新的fiber节点
  if (element.type === REACT_FRAGMENT_TYPE) {
    // 若新节点的类型是 REACT_FRAGMENT_TYPE
    // 则调用 createFiberFromFragment() 方法创建fiber节点
    const created = createFiberFromFragment(
      element.props.children,
      returnFiber.mode,
      lanes,
      element.key
    );
    created.return = returnFiber;
    return created;
  } else {
    // // 若新节点是其他类型，如普通的html元素、函数组件、类组件等
    // 则会调用 createFiberFromElement()
    const created = createFiberFromElement(element, returnFiber.mode, lanes);
    created.ref = coerceRef(returnFiber, currentFirstChild, element);
    created.return = returnFiber;
    return created;
  }
}

在这里，复用的基本流程如下所示：

1. 通过 deleteRemainingChildren(returnFiber, child.sibling) 删除后续节点，因为走到这个节点的时候说明前面的节点已经再 while 循环中的 else 逻辑咯,把匹配不上的节点标记为删除了。并且当前 Fiber 节点只有一个 Fiber 子节点，因此找到可复用的子节点后，可以标记删除掉剩下的(sibling) Fiber 子节点。
2. 调用 useFiber 方法来复用子节点。
3. 通过 existing.return = returnFiber 建立 Fiber 子节点 existing 与当前 Fiber 节点returnFiber 的父子关系 return 属性。

请看下面这个例子：

// 挂载时
const App = () => {
  return (
    <main>
      <h1 />
      <p></p>
    </main>
  );
};

// 更新时
const App = () => {
  return (
    <header>
      <h1 />
      <p></p>
    </header>
  );
};

在这种情况下，虽然只是外层的 main 标签变成了 header 标签，内部的都没有变化，但 React 在进行对比时，还是认为没有匹配上，然后把 main 对应的 fiber 节点及所有的子节点都删除了，重新从 header 标签开始构建新的 fiber 节点。

useFiber

在前面的内容中我们讲到了复用 Fiber 子节点所调用的是 useFiber 方法，下面是该函数的具体实现，如下所示：

function useFiber(fiber: Fiber, pendingProps: mixed): Fiber {
  const clone = createWorkInProgress(fiber, pendingProps);
  clone.index = 0; // 当前子节点必然为第一个子节点
  clone.sibling = null; // 当前子节点没有sibling
  return clone;
}

这个函数做的事情很简单，就是调用 createWorkInProgress 方法，基于旧基于旧 fiber 节点和新内容的 props，克隆生成一个新的 fiber 节点，从而实现旧节点的复用。

并在返回新的 fiber 节点前将其 index 属性重置为 0，sibling 属性重置为 null。将 index 属性重置为 0，使其作为子节点的第一个节点。将 sibling 属性设置为 null，这表示它在创建时没有兄弟节点。

createWorkInProgress

export function createWorkInProgress(current: Fiber, pendingProps: any): Fiber {
  let workInProgress = current.alternate;
  if (workInProgress === null) {
    workInProgress = createFiber(
      current.tag,
      pendingProps,
      current.key,
      current.mode
    );
    workInProgress.elementType = current.elementType;
    workInProgress.type = current.type;
    workInProgress.stateNode = current.stateNode;

    workInProgress.alternate = current;
    current.alternate = workInProgress;
  } else {
    workInProgress.pendingProps = pendingProps;
    workInProgress.type = current.type;

    workInProgress.flags = NoFlags;

    workInProgress.subtreeFlags = NoFlags;
    workInProgress.deletions = null;

    if (enableProfilerTimer) {
      workInProgress.actualDuration = 0;
      workInProgress.actualStartTime = -1;
    }
  }

  workInProgress.flags = current.flags & StaticMask;
  workInProgress.childLanes = current.childLanes;
  workInProgress.lanes = current.lanes;

  workInProgress.child = current.child;
  workInProgress.memoizedProps = current.memoizedProps;
  workInProgress.memoizedState = current.memoizedState;
  workInProgress.updateQueue = current.updateQueue;

  const currentDependencies = current.dependencies;
  workInProgress.dependencies =
    currentDependencies === null
      ? null
      : {
          lanes: currentDependencies.lanes,
          firstContext: currentDependencies.firstContext,
        };

  workInProgress.sibling = current.sibling;
  workInProgress.index = current.index;
  workInProgress.ref = current.ref;

  if (enableProfilerTimer) {
    workInProgress.selfBaseDuration = current.selfBaseDuration;
    workInProgress.treeBaseDuration = current.treeBaseDuration;
  }

  return workInProgress;
}

1. 首先获取 current Fiber 树 的副本作为 workInProgress Fiber 树。如果存在，就表示可以复用它，无需创建新的。
2. 如果 workInProgress === null，调用 createFiber() 函数，基于旧节点的 tag、key、mode 属性和新内容的 props，构建一个新的 fiber 节点，然后复用旧节点的其它属性，并将当前的 current Fiber 树 和 workInProgress Fiber 树通过 alternate 属性连接起来。
3. 如果 workInProgress 不为 null，则直接将 current 的副本作为 workInProgress ，然后复用旧节点的属性。

在该函数中会调用 createFiber 函数构建一个新的 fiber 节点，该函数又返回 new FiberNode(tag, pendingProps, key, mode);` 的返回结果。

Fiber 节点无法复用怎么办

在前面的两个目录中我们都是假定了能 Fiber 节点的情况下，那么如果没有可服用的子节点呢，它会进入创建新的节点的逻辑：

而实现创建新 Fiber 节点逻辑的主要函数使用的是 createFiberFromElement 方法，它的代码如下所示：

export function createFiberFromElement(
  element: ReactElement,
  mode: TypeOfMode,
  lanes: Lanes
): Fiber {
  let owner = null;
  const type = element.type;
  const key = element.key;
  const pendingProps = element.props;
  const fiber = createFiberFromTypeAndProps(
    type,
    key,
    pendingProps,
    owner,
    mode,
    lanes
  );
  return fiber;
}

先来看看我们项目中的代码,如下图所示：

在该函数，通过打印 element 有如下结果所示：

综上所示 createFiberFromElement 函数是用于将 React 元素转换为 Fiber 节点的一部分，它将元素的类型、属性等信息包装到一个 Fiber 节点中，最后返回该节点。

这里单个节点的处理方式算是讲完了，那么 reconcileSingleElement 这个函数从源码注释里就说明了它不是一个递归函数，他只处理当前层级的数据。

而处理递归逻辑的是 performUnitOfWork 函数，如下所示：

处理并列多个元素 reconcileChildrenArray

考虑一下，在我们羡慕中有这样的 jsx 结构，如下代码所示：

import React, { useState } from "react";

const App = () => {
  return (
    <div>
      <div key="a">aa</div>
      <div key="b">bb</div>
      <div key="c">cc</div>
      <div key="d">dd</div>
    </div>
  );
};

通过打印 newChildren 会有如下数据结构输出:

它的 props.children 是一个数组形式的。就说明下一个要构建的 element 是一个数组形式的，即并列多个节点要进行处理。

这种情况要比之前处理单个节点复杂的多，因为可能会存在末尾新增、中间插入、删除、节点移动等情况，比如要考虑的情况有：

• 新列表和旧列表都是顺序排布的，但新列表更长，这里在新旧对比完成后，还得接着新建新增的节点；
• 新列表和旧列表都是顺序排布的，但新列表更短，这里在新旧对比完成后，还得删除旧列表中多余的节点；
• 新列表中节点的顺序发生了变化，那就不能按照顺序一一对比了；

所以就会有以下四个可能性：

• 节点更新：

  旧： A - B - C
  新： A - B - C
  

• 新增节点

  旧： A - B - C
  新： A - B - C - D - E
  

• 删除节点

  旧： A - B - C - D - E
  新： A - B - C
  

• 节点移动

  旧： A - B - C - D - E
  新： A - B - D - C - E
  

在开始之前，首先我们先来看看该函数所接收的参数都有啥:

function reconcileChildrenArray(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChildren: Array<*>,
  lanes: Lanes
): Fiber | null {
  // 新构建出来的fiber链表的头节点
  let resultingFirstChild: Fiber | null = null;
  // 新构建出来链表的最后那个fiber节点，用于构建整个链表
  let previousNewFiber: Fiber | null = null;

  // ...
}

其中 currentFirstChild 代表旧链表的节点，刚开始指向到第 1 个节点。

returnFiber 是它的指向的父元素，也就是父 Fiber：

节点更新

第一轮从头开始遍历 newChildren，会逐个与 oldFiber 链中的节点进行比较，判断节点的 key 或者 tag 是否有变化。

// 旧链表的节点，刚开始指向到第1个节点
let oldFiber = currentFirstChild;
// 表示当前已经新建的 Fiber 的 index 的最大值，用于判断是插入操作，还是移动操作等
let lastPlacedIndex = 0;
// 表示遍历 newChildren 的索引指针
let newIdx = 0;
// 下次循环要处理的fiber节点
let nextOldFiber = null;

for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
  if (oldFiber.index > newIdx) {
    // oldIndex 大于 newIndex，那么需要旧的 fiber 等待新的 fiber，一直等到位置相同
    nextOldFiber = oldFiber;
    // 说明旧 element 对应的newIdx的位置的 fiber 为null，这时将 oldFiber 设置为null，
    oldFiber = null;
  } else {
    // 旧 fiber 的索引和newChildren 的索引匹配上了，获取 oldFiber 的下一个兄弟节点
    nextOldFiber = oldFiber.sibling;
  }

  /**
   * 将旧节点和将要转换的 element 传进去，
   * 1. 若 key 对应上
   * 1.1 若 type 对应上，则复用之前的节点；
   * 1.2 若 type 对应不上，则直接创建新的fiber节点；
   * 2. 若 key 对应不上，无法复用，返回 null；
   * 3. 若 oldFiber 为 null，则直接创建新的fiber节点；
   */
  const newFiber = updateSlot(
    returnFiber,
    oldFiber,
    newChildren[newIdx],
    lanes
  );

  if (newFiber === null) {
    /**
     * 新fiber节点为 null，退出循环。
     * 不过这里为null的原因有很多，比如：
     * 1. newChildren[newIdx] 本身就是无法转为 fiber 的类型，如null, boolean, undefined等；
     * 2. oldFiber 和 newChildren[newIdx] 的 key 没有匹配上；
     */
    if (oldFiber === null) {
      oldFiber = nextOldFiber;
    }
    break;
  }

  if (shouldTrackSideEffects) {
    if (oldFiber && newFiber.alternate === null) {
      deleteChild(returnFiber, oldFiber);
    }
  }

  // 此方法是一种顺序优化手段，lastPlacedIndex 一直在更新，初始为 0，
  // 表示访问过的节点在旧集合中最右的位置（即最大的位置）
  lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);

  if (previousNewFiber === null) {
    // 若整个链表为空，则头指针指向到newFiber
    resultingFirstChild = newFiber;
  } else {
    // 若链表不为空，则将newFiber放到链表的后面
    previousNewFiber.sibling = newFiber;
  }

  // 指向到当前节点，方便下次拼接
  previousNewFiber = newFiber;
  // 下一个旧fiber节点
  oldFiber = nextOldFiber;
}

接下来我们来看一个例子:

旧： A - B - C - D - E
新： A - B - D - C

在本轮遍历中，会遍历 A - B - D - C。A 和 B 都是 key 没变的节点，可以直接复用，但当遍历到 D 时，发现 key 变化了，跳出当前遍历。例子中 A 和 B 是自身发生更新的节点，后面的 D 和 C 我们看到它的位置相对于 oldFiber 链发生了变化，会往下走到处理移动节点的循环中。

这是 diff 算法中的第一次遍历。

每当处理到最后一个固定节点时，要记住此时它的位置，这个位置就是 lastPlacedIndex。

节点删除

若经过上面的循环后，新节点已全部创建完毕，这说明可能经过了删除操作，新节点的数量更少，这里我们直接把剩下的旧节点删除了就行。

if (newIdx === newChildren.length) {
  // 删除旧链表中剩余的节点
  deleteRemainingChildren(returnFiber, oldFiber);
  if (getIsHydrating()) {
    const numberOfForks = newIdx;
    pushTreeFork(returnFiber, numberOfForks);
  }
  // 返回新链表的头节点指针
  return resultingFirstChild;
}

后续已不需要其他的操作了，直接返回新链表的头节点指针即可。

节点新增

新增节点的场景也很好理解，当 oldFiber 链遍历完，但 newChildren 还没遍历完，那么余下的节点都属于新插入的节点，会新建 fiber 节点并以 sibling 为指针连成 fiber 链。

旧： A - B - C 新： A - B - C - D - E

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

  if (getIsHydrating()) {
    const numberOfForks = newIdx;
    pushTreeFork(returnFiber, numberOfForks);
  }
  return resultingFirstChild;
}

节点移动

若节点的位置发生了变动，虽然在旧节点链表中也存在这个节点，但若按顺序对比时，确实不方便找到这个节点。因此可以把这些旧节点放到 Map 中，然后根据 key 或者 index 获取。

const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

该函数首先会调用 mapRemainingChildren 方法返回一个 Map 对象，在项目中有如下代码：

const App = () => {
  const [state, setState] = useState(true);
  return (
    <div onClick={() => setState(!state)}>
      {state ? (
        <>
          <div key="a">aa</div>
          <div key="b">bb</div>
          <div key="c">cc</div>
          <div key="d">dd</div>
        </>
      ) : (
        <>
          <div key="a">aa</div>
          <div key="c">cc</div>
          <div key="d">dd</div>
          <div key="b">bb</div>
        </>
      )}
    </div>
  );
};

它会根据不同的状态显示不同的顺序，当我们点击的时候，会返回一个 existingChildren 的 Map 对象，如下图所示：

把所有的旧 fiber 节点存储到 Map 中后，就接着循环新数组 newChildren，然后从 map 中获取到对应的旧 fiber 节点，也可能不存在，再创建出新的节点。

for (; newIdx < newChildren.length; newIdx++) {
  // 从 map 中查找是否存在可以复用的fiber节点，然后生成新的fiber节点
  const newFiber = updateFromMap(
    existingChildren,
    returnFiber,
    newIdx,
    newChildren[newIdx],
    lanes
  );

  // 这里只处理 newFiber 不为null的情况
  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;
  }

  if (shouldTrackSideEffects) {
    existingChildren.forEach((child) => deleteChild(returnFiber, child));
  }

  return resultingFirstChild;
}

1. 从 map 中查找是否存在可以复用的 fiber 节点，然后生成新的 fiber 节点。
2. 只有当 newFiber 不为空的情况下才会进入该逻辑。
3. 若 shouldTrackSideEffects 为真且 newFiber.alternate !== null，则说明已经复用了该 Fiber 节点，直接从 map 中删除，因为后面会把 map 中剩余为复用的节点删除掉。
4. 更新 lastPlacedIndex。
5. 对之前的 Fiber 进行拼接，如果为 null 则直接创建，若链表不为空，则将 newFiber 放到链表的后面。
6. 到这里整个 diff 算法已经完成了，返回 resultingFirstChild。

如下图所示，它返回了一个全新的 Fiber 树，如下图所示：

参考文章

• React18 源码解析之 reconcileChildren 生成 fiber 的过程
• 深入理解 React Diff 算法
• stack overflow

总结

React 的 diff 算法分为两个阶段：

• 第一个阶段一一对比，如果可以复用就下一个，不可以复用就结束。
• 第二个阶段把剩下的老 fiber 放到 map 里，遍历剩余的虚拟 DOM，查找 map 中是否有可复用的节点。最后把剩下的老 fiber 删掉。

下面再举个例子，如下所示：

旧 A - B - C - D - E - F 新 A - B - D - C - E

第一阶段会一一对比，对比到 B 之后，发现之后的都不对应了,就要跳出这个阶段了。

在第二个阶段开始前，要获取到一个 map 对象，里面存储者 C - D - E - F，接着通过键值对的方式去获取到对应的 Fiber 节点，如果存在则复用。

虚拟 DOM 很好的原因在于它让我们的编码看起来好像是在重新渲染整个场景。在幕后，我们希望计算一个补丁操作，以更新 DOM 使其看起来符合我们的期望。虽然虚拟 DOM 的差异/补丁算法可能不是最优的解决方案，但它为我们提供了一种非常好的表达应用程序的方式。我们只需声明我们想要的精确内容，React/virtual-dom 将会计算出如何使您的场景看起来像这样。我们不必手动进行 DOM 操作，也不必混淆先前的 DOM 状态。我们也不必重新渲染整个场景，这可能比打补丁要低效得多。