What is React Diffing Algorithm ?

What is React Diffing Algorithm ?

React implements a heuristic O(n) algorithm based on two assumptions:

1. Two elements of different types will produce different trees.
2. The developer can hint at which child elements may be stable across different renders with a key prop.

React的diff算法是为了找出两棵虚拟DOM树之间的最小差异。完全比较两棵树的时间复杂度是O(n^3)，但这对于性能要求高的前端应用是不可接受的。因此，React进行了一些优化。

核心优化点：

1. 只比较同一层级：React不会跨层级进行对比。例如，它不会试图将一个父元素的子元素与另一个父元素比较。这简化了问题并将算法的时间复杂度降低到O(n)。
2. key属性：在列表中，React使用key来帮助识别元素。当元素的位置发生改变时，有了key，React可以准确地知道哪些元素是新增的、哪些被移动了、哪些被删除了。

简化后的答案：React的diff算法的时间复杂度是O(n)，主要是因为它只在同一层级进行元素的比较，并利用key来快速识别和比较列表中的元素。

https://zh-hans.reactjs.org/docs/reconciliation.html#the-diffing-algorithm

https://reactjs.org/docs/reconciliation.html#the-diffing-algorithm

https://beta.reactjs.org/learn/preserving-and-resetting-state state 是按位置存的，如果是同级别同类型元素还要考虑 key 的影响

当根节点为不同类型的元素时，React 会拆卸原有的树并且建立起新的树。举个例子，当一个元素从 <a> 变成 <img>，从 <Article> 变成 <Comment>，或从 <Button> 变成 <div> 都会触发一个完整的重建流程。

当卸载一棵树时，对应的 DOM 节点也会被销毁。组件实例将执行 componentWillUnmount() 方法。当建立一棵新的树时，对应的 DOM 节点会被创建以及插入到 DOM 中。组件实例将执行 UNSAFE_componentWillMount() 方法，紧接着 componentDidMount() 方法。所有与之前的树相关联的 state 也会被销毁。

在根节点以下的组件也会被卸载，它们的状态会被销毁。比如，当比对以下更变时：

1<div>
2  <Counter />
3</div>
4
5<span>
6  <Counter />
7</span>

React 会销毁 Counter 组件并且重新装载一个新的组件。

注意：

这些方法被认为是过时的，在新的代码中应该避免使用它们：

• UNSAFE_componentWillMount()

当对比两个相同类型的 React 元素时，React 会保留 DOM 节点，仅比对及更新有改变的属性。

当一个组件更新时，组件实例会保持不变，因此可以在不同的渲染时保持 state 一致。React 将更新该组件实例的 props 以保证与最新的元素保持一致，并且调用该实例的 UNSAFE_componentWillReceiveProps()、UNSAFE_componentWillUpdate() 以及 componentDidUpdate() 方法。

下一步，调用 render() 方法，diff 算法将在之前的结果以及新的结果中进行递归。

默认情况下，当递归 DOM 节点的子元素时，React 会同时遍历两个子元素的列表；当产生差异时，生成一个 mutation。

在子元素列表末尾新增元素时，更新开销比较小。比如：

1<ul>
2  <li>first</li>
3  <li>second</li>
4</ul>
5
6<ul>
7  <li>first</li>
8  <li>second</li>
9  <li>third</li>
10</ul>

React 会先匹配两个 <li>first</li> 对应的树，然后匹配第二个元素 <li>second</li> 对应的树，最后插入第三个元素的 <li>third</li> 树。

如果只是简单的将新增元素插入到表头，那么更新开销会比较大。比如：

1<ul>
2  <li>Duke</li>
3  <li>Villanova</li>
4</ul>
5
6<ul>
7  <li>Connecticut</li>
8  <li>Duke</li>
9  <li>Villanova</li>
10</ul>

React 并不会意识到应该保留 <li>Duke</li> 和 <li>Villanova</li>，而是会重建每一个子元素。这种情况会带来性能问题。

In order to solve this issue, React supports a key attribute. When children have keys, React uses the key to match children in the original tree with children in the subsequent tree. For example, adding a key to our inefficient example above can make the tree conversion efficient:

1<ul>
2  <li key="2015">Duke</li>
3  <li key="2016">Villanova</li>
4</ul>
5
6<ul>
7  <li key="2014">Connecticut</li>
8  <li key="2015">Duke</li>
9  <li key="2016">Villanova</li>
10</ul>

Now React knows that the element with key '2014' is the new one, and the elements with the keys '2015' and '2016' have just moved.

In practice, finding a key is usually not hard. The element you are going to display may already have a unique ID, so the key can just come from your data:

1<li key={item.id}>{item.name}</li>

When that’s not the case, you can add a new ID property to your model or hash some parts of the content to generate a key. The key only has to be unique among its siblings, not globally unique.

As a last resort, you can pass an item’s index in the array as a key. This can work well if the items are never reordered, but reorders will be slow.

Reorders can also cause issues with component state when indexes are used as keys. Component instances are updated and reused based on their key. If the key is an index, moving an item changes it. As a result, component state for things like uncontrolled inputs can get mixed up and updated in unexpected ways.

Here is an example of the issues that can be caused by using indexes as keys on CodePen, and here is an updated version of the same example showing how not using indexes as keys will fix these reordering, sorting, and prepending issues.

React 可以在每个 action 之后对整个应用进行重新渲染，得到的最终结果也会是一样的。在此情境下，重新渲染表示在所有组件内调用 render 方法，这不代表 React 会卸载或装载它们。React 只会基于以上提到的规则来决定如何进行差异的合并。

我们定期优化启发式算法，让常见用例更高效地执行。在当前的实现中，可以理解为一棵子树能在其兄弟之间移动，但不能移动到其他位置。在这种情况下，算法会重新渲染整棵子树。

由于 React 依赖启发式算法，因此当以下假设没有得到满足，性能会有所损耗。

1. 该算法不会尝试匹配不同组件类型的子树。如果你发现你在两种不同类型的组件中切换，但输出非常相似的内容，建议把它们改成同一类型。在实践中，我们没有遇到这类问题。
2. Key 应该具有稳定，可预测，以及列表内唯一的特质。不稳定的 key（比如通过 Math.random() 生成的）会导致许多组件实例和 DOM 节点被不必要地重新创建，这可能导致性能下降和子组件中的状态丢失。

1/**
2 * 创建fiber节点
3 * @param {WorkTag} tag
4 * @param {mixed} pendingProps
5 * @param {null | string} key
6 * @param {TypeOfMode} mode
7 * @constructor
8 */
9function FiberNode(tag: WorkTag, pendingProps: mixed, key: null | string, mode: TypeOfMode) {
10  // Instance
11  this.tag = tag; // 当前节点的类型，如 FunctionComponent, ClassComponent 等
12
13  /**
14   * 这个字段和 react element 的 key 的含义和内容有一样（因为这个 key 是
15   * 从 react element 的key 那里直接拷贝赋值过来的），作为 children 列表
16   * 中每一个 item 的唯一标识。它被用于帮助 React 去计算出哪个 item 被修改了，
17   * 哪个 item 是新增的，哪个 item 被删除了。
18   * @type {string}
19   */
20  this.key = key;
21  this.elementType = null;
22
23  /**
24   * 当前fiber节点的元素类型，与React Element里的type类型一样，若是原生的html标签，
25   * 则 type 为该标签的类型（'div', 'span' 等）；若是自定义的Class Component或
26   * Function Component等，则该type的值就是该class或function，后续会按照上面的tag字段，
27   * 来决定是用new初始化一个实例（当前是 Class Component），然后执行该class内
28   * 的render()方法；还是执行该type（当前是 Function Component），得到其返回值；
29   */
30  this.type = null;
31
32  /**
33   * 1. 若当前fiber节点是dom元素，则对应的是真实DOM元素；
34   * 2. 若当前是function component，则值为null；
35   * 3. 若当前是class component，则值为class初始化出来的实例
36   */
37  this.stateNode = null;
38
39  /**
40   * 下面的return, child和sibling都是指针，用来指向到其他的fiber节点，
41   * React会将jsx编译成的element结构，转为以fiber为节点的链表结构，
42   * return: 指向到父级fiber节点；
43   * child: 指向到该节点的第1个子节点；
44   * sibling: 指向到该节点的下一个兄弟节点；
45   * 如图所示：https://pic4.zhimg.com/80/v2-a825372d761879bd1639016e6db93947_1440w.jpg
46   */
47  this.return = null;
48  this.child = null;
49  this.sibling = null;
50  this.index = 0;
51
52  this.ref = null;
53
54  this.pendingProps = pendingProps;
55  this.memoizedProps = null;
56  this.updateQueue = null;
57  this.memoizedState = null;
58  this.dependencies = null;
59
60  this.mode = mode;
61
62  // Effects
63  this.flags = NoFlags; // 该节点更新的优先级，若为NoFlags时，则表示不更新
64  this.subtreeFlags = NoFlags; // 子节点的更新情况，若为NoFlags，则表示其子节点不更新，在diff时可以直接跳过
65  this.deletions = null; // 子节点中需要删除的节点
66
67  this.lanes = NoLanes;
68  this.childLanes = NoLanes;
69
70  /**
71   * 双缓冲：防止数据丢失，提高效率（之后Dom-diff的时候可以直接比较或者使用
72   * React在进行diff更新时，会维护两颗fiber树，一个是当前正在展示的，一个是
73   * 通过diff对比后要更新的树，这两棵树中的每个fiber节点通过 alternate 属性
74   * 进行互相指向。
75   */
76  this.alternate = null;
77}

jsx 中的所有节点都会转为 fiber 节点，那他们是怎么组合起来的呢？

正如上面代码中的注释中说到的，每个 fiber 节点都有 3 个指针：

• return: 指向到父级的 fiber 节点；
• child: 指向到该节点的第 1 个子节点；若想访问其他的子节点，可以通过下面的sibling指针来访问；
• sibling: 指向到该节点的下一个兄弟节点；

如图所示:

并列的节点，会形成单向链表，父级节点只会指向到这个单向链表的头节点。正如上图中的 p 标签和 span 标签。

• 优点：处理了浏览器的兼容性，防范 xss 攻击，跨平台，差异化更新，减少更新的 dom 操作；
• 缺点：额外的内存，初次渲染不一定快；因为要进行后续一系列的构建、hooks 的搭建等，才会渲染 DOM；会比直接操作 DOM 要慢一些；

为了解决 Stack Reconciler 中固有的问题，以及一些历史遗留问题，在 React 16 版本推出了新的 Reconciliation 算法的调和器—— Fiber 调和器（Fiber Reconciler）来替代栈调和器。Fiber Reconciler 将会利用调度器（Scheduler）来帮忙处理组件渲染/更新的工作。此外，引入 fiber 这个概念后，原来的 react element tree 有了一棵对应的 fiber node tree。在 diff 两棵 react element tree 的差异时，Fiber Reconciler 会基于 fiber node tree 来使用 diff 算法，通过 fiber node 的 return、child、sibling 属性能更方便的遍历 fiber node tree，从而更高效地完成 diff 算法。

fiber 调度的优点：

1. 能够把可中断的任务切片处理;
2. 能够调整任务优先级，重置并复用任务；
3. 可以在父子组件任务间前进后退切换任务；
4. render 方法可以返回多个元素（即可以返回数组）；
5. 支持异常边界处理异常；