React Reconciliation | guanghechen

预备知识
¶

Reconciliation
¶

使用 React 构建的应用，在初次渲染时 React 会调用的 render() 方法生成一棵 React Elements 树，在下一次 props, state 发生变化时，将重新调用 render() 方法并得到一棵新的 React Elements 树。为了高效地完成更新，需要计算出两棵树之间的差异，然后仅对差异部分应用更新。收集差异的过程被称为 Reconciliation（React@15 及其之前的协调算法又被称为 Stack Reconciler），有些地方也直接将它等同于 diffing 算法。

还有一个关于 Reconciliation 的定义：React 拥有多个渲染器，如 react-dom 负责 web 端渲染，react-native 负责移动端渲染，它们都是依赖具体平台的，但中间有大量的逻辑是平台无关的，可以进行复用的，如协调算法（Diffing），自定义组件、state、生命周期方法和 refs 等特性；这部分共享的逻辑称为 Reconciler。

Scheduling
¶

在前端应用中存在多种类型的任务，如用户交互、动画、网络请求、后台计算任务等，为了得到更好的用户体验，有些任务具有更高的优先级，如动画应该优先于依赖网络请求的任务 ^[1]，用户交互优于后台计算任务等。Scheduling 过程是给任务安排执行的顺序和时机，使得高优先级的任务优先得到执行。

React 使用 pull 模型来构建 UI，使得计算动作可以推迟到需要的时候再执行^[2]，比如某些元素在屏幕外面，则可以拖迟所有与它相关的计算动作。尽管理论上 React 拥有这样的能力，但是在 Stack Reconciliation 算法中，React 使用了原生的函数栈进行递归处理，使得所有的动作都在单一工作流中，无法被打断，也就无法使用这样的能力^[3]。

计算两棵树之间的差异
¶

计算从一棵树转换成另一个树所需要的最小操作次数的问题，即便使用最优算法（树的最小编辑距离算法)，其复杂度也达到了 $O (N^{3})$ ，这样是的复杂度是无法承受的。为了快速完成两棵树的对比， React 提出了一个 $O (N)$ 的启发式算法，这基于以下两个假设：

两个不同类型的元素对应两棵不同的树；
开发者可通过 key 属性来显式地告知 React 哪些子元素在不同的渲染过程中可以保持不变；

上述的启发式算法实际上是通过放弃最优解而达到降低复杂度的目的：

其第一个假设本质上相当于“树中节点跨层级变动的可能性是很小的”（实际上也与实际情况相符），从而将差异对比限制在同层级的兄弟节点列表中，此时复杂度降为 $O (N^{2})$ （这是一个宽松上界）。
第二个假设相当于提供了一个安全舱口，让开发者自行判断哪些同级节点是可以复用的，以避免后续高昂的卸载旧树、重建新树的操作。同时，因为要求指定 key（默认情况下可以认为使用其在父节点的子节点列表中的索引作为 key），因此仅需考虑那些在旧树中相同 key 的节点；这部分也是我没有想清楚的，假设新旧子元素列表长度为别为 $k_{1}, k_{2}$ ，则这个比较过程复杂度应是 $O (k_{1} \cdot k_{2})$ 的。
尽管如此，对于同层级节点的比较至少存在一个优化策略（没有看源码，不知道 React 是否采用了此策略）：
不妨记两个元素列表分别为： $A = {a_{1}, a_{2}, \dots, a_{k_{1}}}$ 和 $B = {b_{1}, b_{2}, \dots, b_{k_{2}}}$
先顺序遍历 $A$ 和 $B$ ，检查同索引情况下（不妨记当前索引为 $i$ ）， $a_{i}$ 和 $b_{i}$ 的 key 是否相同，若相同，则直接复用此节点；若不相同，将 ${b_{i}, b_{i + 1}, \dots, b_{k_{2}}}$ 建立成 $< k e y, x >$ 的 hash 表，其中 $x$ 表示 $B$ 的下标，然后依次检查 ${a_{i}, a_{i + 1}, \dots a_{k_{1}}}$ 均通过 hash 表进行判断），若存在，则复用，否则新建节点。
这个优化将创建 hash 表的动作延迟到同层级节点 key 的顺序发生变化时进行，若同层级节点的结构保持一致，key 值没有发生改变，则相当于一次普通的遍历就完成了 diff 动作，此时总复杂度降为 $O (N)$ 。
上面的 hash 表使用 $B$ 的下标作为值，是因为这样可以快速判断 $a_{i}$ 对应的 $b_{x}$ ，其在 $i$ 的后面还是前面，若在 $i$ 的前面，则先进行一次移动，再进行更新。

The Diffing Algorithm
¶

在对比两棵树时，React 首先比较它们的根节点。针对根节点元素的各种比较结果，应用不同的比较策略。

元素类型不同
¶

当两个根节点为不同类型的元素时，React 会卸载原树，并从头建立一棵新树。比如一个元素从 <a> 变成 <img>，从 <Article> 变成 <Comment> 或是从 <Button> 变成 <div>，都会触发完整的重建流程：

卸载一棵树时，所有旧 DOM 节点都会被销毁；旧组件实例的生命周期函数 componentWillUnmount() 会得到调用
建立一棵新树时，所有新的 DOM 节点会被插入到 DOM 中；旧组件实例的生命周期函数 UNSAFE_componentWillMount() 会得到调用，紧接着，其 componentDidMount() 函数也将得到触发。所有与之前的树相关联的 state 都会被销毁。

根节点下的所有组件都会按照上述方式被卸载、重建，它们的状态也都会被销毁。比如，当对比下列变更时：

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

<span>
  <Counter />
</span>

Counter 组件将被销毁并被重建。

类型相同的 DOM 元素
¶

当对比两个相同类型的 React DOM 元素时，React 会保留底层的（underlying） DOM 节点，而仅对比它们的属性（DOM attributes）差异，并仅更新属性的差异部分。如：

1
2
3
<div className="before" title="stuff" />

<div className="after" title="stuff" />

在对比上面两个元素时，React 知道仅需修改底层的 DOM 节点的 className 属性。

在更新 style 属性时，React 知道仅需更新 style 的差异部分。如：

1
2
3
<div style={{color: 'red', fontWeight: 'bold'}} />

<div style={{color: 'green', fontWeight: 'bold'}} />

在转换上述两个节点时，React 知道仅需修改 color 属性，而无需修改 fontWeight 属性。

在处理完当前的 DOM 节点时，React 继续对其子节点进行递归处理。

类型相同的组件元素
¶

当一个组件更新时，其实例会保持不变，因此在不同的渲染过程中其 state 也将保持不变。 React 将更新组件实例的 props 以保证与新的元素一致，并依次调用组件的 UNSAFE_componentWillReceiveProps()、UNSAFE_componentWillUpdate()、 componentDidUpdate() 方法。

紧接着，调用组件的 render() 方法，并对其返回的结果与之前的结果递归应用 Diffing 算法。

处理子元素
¶

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

因为是按照顺序遍历的，因此在末尾插入元素时，更新开销更小，因为前面的元素可以在遍历中尽可能复用；而若是在首部插入元素，更新开销最大，因为前面的所有元素都将失配。如下面的列子中，在首部插入了 <li>Connecticut</li>：

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

<ul>
  <li>Connecticut</li>
  <li>Duke</li>
  <li>Villanova</li>
</ul>

React 并不能意识到 <li>Duke</li> 和 <li>Villanova</li> 应该被复用，而是将重建它们。

Keys
¶

为了解决上述问题，React 引入了 key 属性。如下面的例子中，React 可以知道需要新插入一个 key="2014" 的节点，而其它两个节点都可以复用。

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

<ul>
  <li key="2014">Connecticut</li>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

在 Introduction 中提到，React 需要通过 key 进行同层级节点比较，因此 key 需要指定为一个稳定的、可预测的值。使用 Math.random() 是一个糟糕的主意。

预备知识¶

Reconciliation¶

Scheduling¶

计算两棵树之间的差异¶

The Diffing Algorithm¶

元素类型不同¶

类型相同的 DOM 元素¶

类型相同的组件元素¶

处理子元素¶

Keys¶

Related¶