基于Fiber的React Diff算法源码分析
一、简介
React15整体架构分为两层：Reconciler（协调器）层和Renderer（渲染器）层，Reconciler负责找出变化的组件，Renderer负责将变化的组件渲染到页面上，其中，Reconciler采用递归的方式创建虚拟DOM，由于递归过程是不能中断的，如果组件树的层级很深，递归会占用线程很多时间，会造成页面卡顿。
为了解决这个问题，React团队决定重写整个架构，基于全新的Fiber架构将无法中断的递归更新重构为异步的可中断更新。于是，Fiber搭载React16版本的顺风车跟大家见面了。
我们都知道Diff算法是为了找出变化的元素，作为Reconciler层重要一环，扮演着重要的角色。本文从源码角度就全新的React Fiber架构和大家聊一聊Diff算法，包含以下三个部分：
React 15和React 16版本的对比
Fiber是什么，以及Fiber节点如何连接成Fiber树
从源码角度介绍下Diff算法的整个过程
二、React15 Vs React16
React15将整体架构分为了两层，如图一所示，react16将整体架构分为了三层，如图二所示：
图二 React16整体架构
React16架构相较于React15增加了Scheduler调度器，用来调度任务，优先级高的任务优先进入Reconciler执行。
在React中每一个DOM树结构，都有对应一个虚拟DOM树结构。React15中使用普通的树结构表示虚拟DOM，虚拟DOM节点的结构如图三所示，React16使用链表结构表示虚拟DOM，由之前的虚拟DOM节点升级为Fiber节点，Fiber节点结构如图四所示。
图三 React15虚拟DOM节点
图四 React16 Fiber虚拟DOM节点
其中，Fiber节点中type属性标识元素的类型，key属性和type属性可唯一标识一个元素，stateNode属性标识Fiber节点对应的真实DOM节点，return、sibling和child分别标识父Fiber节点、兄弟Fiber节点和子Fiber节点。flags用来标记Fiber节点对应的真实DOM节点将要被执行的DOM操作，常见的操作有Placement（插入）、Deletion（删除）和Update（更新）等，对应的flags值分别为：5、8和4。
在React15中，Reconciler采用递归的方式更新子组件，更新一旦开始，中途就无法中断。React16利用Scheduler和基于Fiber节点的链表结构的虚拟DOM实现了可中断异步更新。
三、Fiber节点构成Fiber树
在第二部分介绍了Fiber节点，那么Fiber节点是如何链接成Fiber树也就是虚拟DOM树呢？我们通过一个例子看一下：
funtion App() {
return ( < div > <span > 贝壳 < /span>
<span>大前端</span > </div>
)
}
上述代码片段中function 组件对应的Fiber树如图五所示。
图五 function App组件对应的Fiber树
由图可以看出Fiber节点是依赖return、sibling和child这三个属性，将Fiber节点连接成Fiber树，即虚拟DOM树。
在React中最多存在两颗Fiber树，当前屏幕上DOM结构对相应的Fiber树称为current Fieber树，在内存中构建的Fiber树称为workInProgress Fiber树。其中，Diff算法的计算过程就是生成workInProgress Fiber树的过程，每次页面状态更新都会产生新的workInProgress Fiber树，当workInProgress Fiber树构建完成后交给Renderer渲染在页面上，之后在React中使用根节点的current指针完成由current Fieber树到workInProgress Fiber树的切换，此时workInProgress Fiber树就成为了current Fiber树，完成DOM更新。
四、基于Fiber的 React Diff
1、概念介绍
首先从概念上介绍下React Diff算法，如图六所示，将要更新的DOM节点在更新时刻与四个节点有关：DOM节点本身，DOM节点对应的JSX对象，DOM节点对应的current Fiber节点以及workInProgress Fiber节点，而Diff 算法的本质是对比JSX对象和current Fiber节点，然后根据对比结果生成workInProgress Fiber节点，进而生成workInProgress Fiber树。其中需要执行相关操作的Fiber节点将会被打上flags标记，之后Renderer渲染器基于Diff 过程中打上flags标记的Fiber节点链接成的链表进行相关的DOM操作。
图六 DOM节点相关节点
2、Diff算法预设
即使在最前沿的算法中，将前后两棵树完全比对的算法的复杂程度为 O(n3)，为了降低算法复杂度，React的Diff会预设三个限制：
（1）只对同级元素进行Diff，Diff 算法只需对比节点当前所在层级；
（2）两个不同类型的元素会产生出不同的树，如果更新前后元素类型发生改变，则会新建节点及其子节点；
（3）开发者可为同层级的节点设置唯一key标识节点，以此暗示哪些子元素在不同的渲染下能保持稳定。
举个例子，如下所示：
// 更新前
<div>
<p key="id1">节点1</p>
<span key="id2">节点2</span>
</div>
// 更新后
<div>
<span key="id2">节点2</span>
<p key="id1">节点1</p>
</div>
如果没有key，React会认为div的第一个子节点由p变为span，第二个子节点由span变为p，按照第二条预设，会新建节点p和节点span。
但若开发者使用了key，指明了节点的对应关系，也就是说节点p和span只是交换了顺序，无需新建，可以进行复用。
通过第一个预设，将DOM树的对比限制在了同一个层级进行对比，算法复杂度变为了O(n)，然后通过第三个预设使得同层级的节点通过自身的key能快速方便的找到变化后的节点。
3、Diff算法入口函数介绍
接下来，介绍下Diff算法入口函数。
根据同级的节点数量将Diff算法分为两类，单节点Diff和多节点Diff：
当newChild类型为object、number、string，代表同级只有一个节点，会调用单节点Diff函数reconcileSingleElement函数
当newChild类型为Array，表示同级有多个节点，会调用多节点Diff函数reconcileChildrenArray函数
入口代码如下述所示：
function reconcileChildFibers(
returnFiber: Fiber,
currentFirstChild: Fiber | null,
newChild: any,
): Fiber | null {
const isObject = typeof newChild === 'object' && newChild !== null;
if (isObject) {
// object类型，可能是 REACT_ELEMENT_TYPE 或 REACT_PORTAL_TYPE
switch (newChild.$typeof) {
case REACT_ELEMENT_TYPE:
// 调用 reconcileSingleElement 处理
// ...其他case
}
}
if (typeof newChild === 'string' || typeof newChild === 'number')
{
// 调用 reconcileSingleTextNode 处理
}
if (isArray(newChild)) {
// 调用 reconcileChildrenArray 处理
}
// 以上都没有命中，删除节点
return deleteRemainingChildren(returnFiber, currentFirstChild);
}
（1）单节点Diff
单节点Diff比较简单，先看下单节点Diff函数，源代码如下所示：
function reconcileSingleElement(
returnFiber: Fiber,
currentFirstChild: Fiber | null,
element: ReactElement
): Fiber {
const key = element.key;
let child = currentFirstChild;
// 首先判断是否存在对应DOM节点
while (child !== null) {
// 上一次更新存在DOM节点，接下来判断是否可复用
// 首先比较key是否相同
if (child.key === key) {
// key相同，接下来比较type是否相同
switch (child.tag) {
// ...省略case
default: {
if (child.elementType === element.type) {
// type相同则表示可以复用
// 返回复用的fiber
return existing;
}
// type不同则跳出switch
break;
}
}
// 不能复用的节点，被标记为删除
deleteRemainingChildren(returnFiber, child);
break;
} else {
// key不同，将该fiber标记为删除
deleteChild(returnFiber, child);
}
child = child.sibling;
}
// 创建新Fiber，并返回 ...省略
}
React首先判断key是否相同，如果key相同则判断type是否相同，只有都相同时一个DOM节点才能复用，如果可以复用，则直接使用currrent Fiber节点，无需在重新创建Fiber节点。
（2）多节点Diff
对于同级有多个元素的节点，Diff 算法要处理的情况相对复杂，但可以总结归纳为三种情况，第一种为节点新增或减少，第二种为节点更新，第三种为节点位置发生变化。举例如下。
情况1 节点更新，如下所示，包括节点属性变化以及节点类型更新：
//更新前
<div>
<span key="id1" className="before"></span>
<span key="id2"></span>
</div>
// 节点属性变化 className 由before 变成了after
<div>
<span key="id1" className="after"></span>
<span key="id2"></span>
</div>
// 节点类型变化 第二个子元素由span 变成了div
<div>
<span key="id1" className="before"></span>
<div key="id2"></div>
<div>
情况2 节点新增或减少，如下所示：
//情况2 节点新增 或减少 更新之前
<div>
<span key="id1"></span>
<span key="id2"></span>
</div>
// 新增节点
<div>
<span key="id1"></span>
<span kye="id2"></span>
<span key="id3"></span>
</div>
//删除节点
<div>
<span key="id1"></span>
</div>
情况3 节点位置变化，如下所示：
// 情况3 节点位置变化 更新之前
<div>
<span key="id1"></span>
<span key="id2"></span>
</div>
// 更新之后 位置发生了变化
<div>
<span key="id2"></span>
<span key="id1"></span>
</div>
页面中所有同级有多个元素的节点的更新情况无非是以上的一种或多种场景的组合。
但是，React团队发现，在日常开发中，相对于增加和删除，更新组件发生的频率更高。所以React Diff会优先判断当前节点是否属于更新。
基于以上原因，Diff算法的整体逻辑会经历两轮遍历：
第一轮遍历：处理更新的节点
第二轮遍历：处理剩下的不属于更新的节点。
1）多节点Diff第一轮遍历
第一轮遍历的目的是处理更新节点，处理流程图如图七所示，其中的newChildren为被转译后的JSX 对象，orderFiber为链表结构的current Fiber树。
图七 React diff 算法流程图
第一轮遍历产生了两个结果，结合例子分析一下，如下所示。
// 更新之前
<div key="id1" className="a">1</div>
<div key="id2" className="b">2</div>
// 更新之后情况1 newChildren与oldFiber都遍历完
<div key="id1" className="aa">1</div>
<div key="id2" className="bb">2</div>
// 更新之后情况2 newChildren没遍历完，oldFiber遍历完
<div key="id1" className="aa">1</div>
<div key="id2" className="bb">2</div>
<div key="id3" className="cc">3</div>
// 更新之后情况3 newChildren遍历完，oldFiber没遍历完
<div key="id1" className="aa">1</div>
结果一：可能newChildren遍历完，或oldFiber遍历完，或他们同时遍历完。
• newChildren与oldFiber同时遍历完，如更新之后情况1。
这是最理想的情况，只需在第一轮遍历进行组件更新，此时Diff结束。
• newChildren没遍历完，oldFiber遍历完，如更新之后情况2。
因为oldFiber树遍历完，所以已有的DOM节点都复用了，同时newChildren没遍历完，表示有新加入的节点，我们只需要遍历剩下的newChildren，并生成新的workInProgress fiber节点，依次标记Placement，此时Diff结束。
• newChildren遍历完，oldFiber没遍历完，如更新之后情况3。
newChildren遍历完，同时oldFiber没遍历完，意味着更新之后的节点比更新之前的节点数量少了，即有节点被删除了。所以需要遍历剩下的oldFiber，依次剩余的olderFiber节点标记Deletion，此时Diff结束。
结果二：因为key不同跳出的遍历，表示此时的newChildren没有遍历完，oldFiber也没有遍历完。
举个例子，如下所示：
//更新之前
<div key="id1">1</div>
<div key="id2">2</div>
<div key="id3">3</div>
//更新之后
<div key="id1">1</div>
<div key="id3">3</div>
<div key="id2">2</div>
newChildren与oldFiber都没遍历完，这意味着有节点在这次更新中改变了位置，需要进行第二轮遍历。
2）多节点Diff第二轮遍历
因为第二轮遍历需要处理改变位置的节点，所以为了方便找到拥有同一个key的newChildren和olderFiber节点，react团队将所有还未处理的oldFiber存入以key为key，oldFiber为value的Map中。
图八 Map结构
图八为打印的Map结构，接下来遍历剩余的newChildren，通过newChildren[i].key就能很快在existingChildren中找到key相同的oldFiber节点。
因为有节点的位置发生了移动，所以需要选一个参照的节点，来判断其他的节点是否移动，React选定最后一个可复用的节点为参照物，记下其在oldFiber中的位置索引，用变量lastPlacedIndex表示。
由于更新中节点是按newChildren的顺序排列，所以在遍历newChildren过程中，每个遍历到的可复用节点一定是当前遍历到的所有可复用节点中最靠右的那个。
用变量oldIndex表示遍历到的可复用节点在oldFiber中的位置索引，如果oldIndex < lastPlacedIndex，代表本次更新该节点需要被移动（标记为Placement），oldIndex > lastPlacedIndex代表该节点不需要被移动。
其中，lastPlacedIndex初始为0，更新lastPlacedIndex规则为：每遍历一个可复用的节点，如果oldIndex >= lastPlacedIndex，则更新lastPlacedIndex为oldIndex，否则，不更新。
结合上面的分析看下源代码，代码中注释了相关代码片段的功能。reconcileChildrenArray 函数入口以及传参和初始化参数。
function reconcileChildrenArray(
returnFiber: Fiber, //父节点
currentFirstChild: Fiber | null, //current Fiber 节点
newChildren: Array<*>, //JSX对象
lanes: Lanes,
): Fiber | null {
// 函数返回的Fiber节点
let resultingFirstChild: Fiber | null = null;
let previousNewFiber: Fiber | null = null;
// oldFiber为链表
let oldFiber = currentFirstChild;
// 用来判断节点是否移动的参照物
let lastPlacedIndex = 0;
let newIdx = 0;
let nextOldFiber = null;
}
多节点Diff第一轮遍历的代码片段如下所示：
// 第一轮遍历，只遍历key相同的节点，key不同即跳出遍历
for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
if (oldFiber.index > newIdx) {
nextOldFiber = oldFiber;
oldFiber = null;
} else {
// 下次循环的旧Fiber节点：当前 oldFiber的兄弟节点
nextOldFiber = oldFiber.sibling;
}
// key相同返回fiber节点，key不同返回null
// 如果type相同复用节点，不同则确定该节点将会被删除，然后返回新节点，将oldFiber删除
const newFiber = updateSlot( // 返回newFiber节点
returnFiber,
oldFiber,
newChildren[newIdx],
lanes,
);
// newFiber为null表示key不同，跳出第一轮循环
if (newFiber === null) {
if (oldFiber === null) {
oldFiber = nextOldFiber;
}
break;
}
// newFiber.alternate为null就是新节点，说明type不同创建了新fiber节点
if (oldFiber && newFiber.alternate === null) {
// 需要把oldFiber标记删除
deleteChild(returnFiber, oldFiber);
}
// 放置节点,更新lastPlacedIndex
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
// 将新fiber链接到Fiber树
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
//nextOldFiber节点为下一个循环的oldFiber节点
oldFiber = nextOldFiber;
}
// 第一轮遍历结束
处理多节点Diff第一轮遍历结果代码片段如下所示：
// 处理第一轮遍历结果
// 若第一轮遍历完后新节点数量少于旧节点数量
// newChildren已经遍历完，将删除掉剩下的fiber节点
if(newIdx === newChildren.length) {
deleteRemainingChildren(returnFiber, oldFiber);
return resultingFirstChild;
}
// 若第一轮遍历完新节点数量大于旧节点数量
// oldFiber已经遍历完,无节点可以复用，则创建新的节点
if (oldFiber === null) {
for (; newIdx < newChildren.length; newIdx++) {
const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
if (newFiber === null) {
continue;
}
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
// 将新fiber链接到Fiber树
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
}
return resultingFirstChild;
}
// 处理第一轮遍历结果完成
多节点Diff第二轮遍历的代码片段如下所示：
// 进行第二轮遍历
// 还未处理的oldFiber存入以key为key，oldFiber为value的Map中，方便用key来获取对应的旧fiber节点
const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
// 进入第二轮遍历，继续遍历剩余的newChildren节点，这些节点可能是需要移动或者删除的
for (; newIdx < newChildren.length; newIdx++) {
// 从map中获取对应对应key的旧节点，返回更新后的新节点
const newFiber = updateFromMap(
existingChildren,
returnFiber,
newIdx,
newChildren[newIdx],
lanes,
);
if (newFiber !== null) {
// 若节点被复用，从map里删除老的节点，对应的情况可能是位置的改变
if (newFiber.alternate !== null) {
// 复用的节点要移除map，因为map里剩余的节点都会被标记Deletion删除
existingChildren.delete(
newFiber.key === null ? newIdx : newFiber.key,
);
}
// 放置节点同时节点判断是否移动
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
// 将新fiber链接到Fiber树
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
}
}
// 结束第二轮遍历
// 删除剩下的无用节点，并标记Deletion删除
existingChildren.forEach(child => deleteChild(returnFiber, child));
return resultingFirstChild;3. 实例分析
下面通过一个例子阐述下整个Diff 过程，为了简化Diff过程，其中的ABCD表示DOM树的节点，字母的值表示节点的key。
如上图所示，app节点下有顺序为ABCD四个节点，若将app节点下变为ADBE，Diff 算法会经历下面的过程。
第一轮遍历
第一轮遍历newChildren开始，节点A可复用，此时的workInProgress Fiber树为
继续遍历下一个节点，因newChildren第二个节点D和oldFiber 中下一个节点B的key不相同跳出第一轮遍历，进行第二轮遍历。
2.第二轮遍历
此时的olderFiber和newChildren如下：
此时lastPlacedIndex为0，Map为{B:B，C:C，D:D}，接下来继续遍历newChildren的下一个节点为D，key为D的节点在Map中存在，D节点的oldIndex为3，oldIndex > lastPlacedIndex，D节点可以复用 ，位置也不需要移动。
此时的workInProgress Fiber树为：
更新lastPlacedIndex为3，此时Map为{B:B，C:C}，继续遍历newChildren下一个节点B，key为B的节点在Map中存在，B节点的oldIndex为1，oldIndex <lastPlacedIndex，所以B节点可复用，但是需要移动，所以为B节点打上Placement 标签。
此时的workInProgress Fiber树为：
lastPlacedIndex依旧为3，此时Map为{C:C}，继续遍历newChildren下一个节点E，key为E的节点在Map中不存在，此时就需要新建E节点，并为E节点打新增标签。
此时的workInProgress Fiber树为：
newChildren遍历完成，此时Map为{C:C}，下一步将older Fiber 中的C节点打上Deletion标签，然后依次收集打上标签的节点，首先会将同级节点上需要删除的节点收集起来，然后依次收集其他打上标签的节点，收集好的节点连接成链表结构，如下图：
Renderer渲染器会依据生成的链表操作真实的DOM，完成页面的更新操作。
四、总结
相较于React15，React16利用Scheduler和基于Fiber节点的链表结构的虚拟DOM实现了可中断异步DOM更新，改善了页面DOM层级过深时造成的页面卡顿现象。React16 中的虚拟DOM树是由Fiber节点链接成的Fiber树，其中的每一个Fiber节点都有与之相对应的真实DOM节点。
在React中最多存在两颗Fiber树，current Fieber树和workInProgress Fiber 树，Diff 算法的本质就是对比current Fieber节点和JSX对象，然后生成workInProgress Fiber树。根据同级的节点数量将Diff算法分为两类，单节点Diff和多节点Diff。
Diff 过程中通过key和type来对节点进行对比，如果更新前后节点的key和type相同，则节点可以被复用，否则，需要重建节点；同时会对需要更新、删除以及移动等操作的Fiber节点打上不同的标记，然后会将这些Fiber节点连接成链表。最后，Renderer渲染器根据生成的链表执行实际的DOM操作，完成更新。