Appearance
在介绍diff之前，我们先声明几个关键词的含义
- currentFiber 当前正在渲染的Fiber节点
- workInProgress Fiber 正在渲染的Fiber节点
- JSX对象 即将要更新的的dom通过jsx的babel转换后的 数组
说白了diff的本质就是比较JSX对象和current Fiber，然后生成workInProgress Fiber
Fiber是什么？
通俗点来说，Fiber就是一个数据结构，它是一个链表，它的作用是用来描述DOM节点的，它的结构如下
js
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;
// 用于连接其他Fiber节点形成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;
// 指向该fiber在另一次更新时对应的fiber
this.alternate = null;
}当然你也可以理解他是一个大对象，上面挂载了react所有的信息，比如dom节点、属性、事件、状态等等。
Fiber
在说diff之前插一嘴Fiber的工作原理，了解了这个可能对diff的理解会更深刻
双缓存
什么是“双缓存”？
当我们用canvas绘制动画，每一帧绘制前都会调用ctx.clearRect清除上一帧的画面。 如果当前帧画面计算量比较大，导致清除上一帧画面到绘制当前帧画面之间有较长间隙，就会出现白屏。
为了解决这个问题，我们可以在内存中绘制当前帧动画，绘制完毕后直接用当前帧替换上一帧画面，由于省去了两帧替换间的计算时间，不会出现从白屏到出现画面的闪烁情况。 这种在内存中构建并直接替换的技术叫做双缓存。
而在react中，Fiber就是利用两个指针（workInProgress和currentFiber）去进行切换的，当我们有更新的时候所有的操作都是在workInProgress这棵树上去进行的，当更新完成后，将workInProgress指向的树赋值给currentFiber，然后将workInProgress指向的树清空，等待下一次更新。
而这个更新过程就是下面内容说的diff算法了，react会根据这个算法去决定Fiber上面那些节点需要更新、新增、删除、移动一类的操作
说到这里，你会发现是一个“对象”和一个数组进行比较，这和vue的diff是不同的，人家那个是两个数组进行比较。
同类型的比较肯定可以用到一些算法去实现效率的提升，比如双指针、二分法等等。
但是不同类型的比较就用不到这种提效的算法了，对此react团队是怎么做的呢，下面带大家分析下
React文档中提到，即使在最前沿的算法中，将前后两棵树完全比对的算法的复杂程度为 O(n 3 )，其中n是树中元素的数量
如果在React中使用了该算法，那么展示1000个元素所需要执行的计算量将在十亿的量级范围。这个开销实在是太过高昂。
为了降低算法复杂度，React的diff会预设三个限制：
- 只对同级元素进行Diff。如果一个DOM节点在前后两次更新中跨越了层级，那么React不会尝试复用这个DOM节点。
- 两个不同类型的元素将会产生出不同的树。如果元素由div变为p，React会销毁旧的树并构建新的树。
- 开发者可以通过key属性来暗示哪些子元素在不同的渲染下能保持稳定。
接下来就是如何比较了
js
// 根据newChild类型选择不同diff函数处理
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);
}上面这一块代码简写就是整个diff的入口函数，我们可以从同级的节点数量将Diff分为两类：
- 当newChild类型为object、number、string，代表同级只有一个节点
- 当newChild类型为Array，同级有多个节点
单节点
对于单个节点，我们以类型object为例，会进入reconcileSingleElement
js
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;
}
}
// 代码执行到这里代表：key相同但是type不同
// 将该fiber及其兄弟fiber标记为删除
deleteRemainingChildren(returnFiber, child);
break;
} else {
// key不同，将该fiber标记为删除
deleteChild(returnFiber, child);
}
child = child.sibling;
}
// 创建新Fiber，并返回 ...省略
}从代码可以看出，React通过先判断key是否相同，如果key相同则判断type是否相同，只有都相同时一个DOM节点才能复用。
有个细节不知道大家注意到没有，就是key相同和不相同的情况下，选择删除的节点是不同的
当child !== null且key相同且type不同时执行deleteRemainingChildren将child及其兄弟fiber都标记删除。
当child !== null且key不同时仅将child标记删除。
为什么呢？ 考虑下这个例子
js
// 上次渲染的
<ul>
<li key="1">1</li>
<li key="2">2</li>
<li key="3">3</li>
</ul>
// 这次需要更新的
<ul>
<p key="1">1</p>
</ul>由于本次更新时只有一个p，属于单一节点的Diff，会走上面介绍的代码逻辑。
在reconcileSingleElement中遍历之前的3个fiber（对应的DOM为3个li），寻找本次更新的p是否可以复用之前的3个fiber中某个的DOM。
当key相同且type不同时，代表我们已经找到本次更新的p对应的上次的fiber，但是p与li type不同，不能复用。既然唯一的可能性已经不能复用，则剩下的fiber都没有机会了，所以都需要标记删除。
如果当key不同时只代表遍历到的该fiber不能被p复用，后面还有兄弟fiber还没有遍历到。所以仅仅标记该fiber删除。
多节点
关于多节点的diff，我们先分析下平时写代码可能会有哪些情况的产生
节点更新
html
<!-- 之前 -->
<ul>
<li key="0" className="before">0<li>
<li key="1">1<li>
</ul>
<!-- 之后 情况1 —— 节点属性变化 -->
<ul>
<li key="0" className="after">0<li>
<li key="1">1<li>
</ul>
<!-- 之后 情况2 —— 节点类型更新 -->
<ul>
<div key="0">0</div>
<li key="1">1<li>
</ul>节点新增或减少
html
<!-- 之前 -->
<ul>
<li key="0" className="before">0<li>
<li key="1">1</li>
</ul>
<!-- 之后 情况1 —— 节点新增 -->
<ul>
<li key="0" className="before">0<li>
<li key="1">1</li>
<li key="2">1</li>
</ul>
<!-- 之后 情况2 —— 节点减少 -->
<ul>
<li key="0" className="before">0</li>
</ul>节点位置变化
html
<!-- 之前 -->
<ul>
<li key="0">0<li>
<li key="1">1<li>
</ul>
<!-- 之后 -->
<ul>
<li key="1">1<li>
<li key="0">0<li>
</ul>同级多个节点的Diff，一定属于以上三种情况中的一种或多种。
有了情况我们大众的思路是不是就去遍历写几个if else？
那么这么做的话会有一个问题，这三种情况的优先级都是一样的，这样就会造成没必要的循环比较，浪费性能
react是怎么做的呢？
在日常开发中，相较于新增和删除，更新组件发生的频率更高。所以Diff会优先判断当前节点是否属于更新。
基于以上原因，Diff算法的整体逻辑会经历两轮遍历：
第一轮遍历：处理更新的节点。
第二轮遍历：处理剩下的不属于更新的节点。
第一轮遍历思路
let i = 0，遍历newChildren，将newChildren[i]与oldFiber比较，判断DOM节点是否可复用。
如果可复用，i++，继续比较newChildren[i]与oldFiber.sibling，可以复用则继续遍历。
如果不可复用，分两种情况：
key不同导致不可复用，立即跳出整个遍历，第一轮遍历结束。
key相同type不同导致不可复用，会将oldFiber标记为DELETION，并继续遍历
如果newChildren遍历完（即i === newChildren.length - 1）或者oldFiber遍历完（即oldFiber.sibling === null），跳出遍历，第一轮遍历结束。
当遍历结束后，会有两种结果：
步骤3跳出的遍历
此时newChildren没有遍历完，oldFiber也没有遍历完。 比如这一种
html
<!-- 之前 -->
<li key="0">0</li>
<li key="1">1</li>
<li key="2">2</li>
<!-- 之后 -->
<li key="0">0</li>
<li key="2">1</li>
<li key="1">2</li>第一个节点可复用，遍历到key === 2的节点发现key改变，不可复用，跳出遍历，等待第二轮遍历处理。
此时oldFiber剩下key === 1、key === 2未遍历，newChildren剩下key === 2、key === 1未遍历。
步骤4跳出的遍历
可能newChildren遍历完，或oldFiber遍历完，或他们同时遍历完。
html
<!-- 之前 -->
<li key="0" className="a">0</li>
<li key="1" className="b">1</li>
<!-- 之后 情况1 —— newChildren与oldFiber都遍历完 -->
<li key="0" className="aa">0</li>
<li key="1" className="bb">1</li>
<!-- 情况2 —— newChildren没遍历完，oldFiber遍历完 -->
<!-- newChildren剩下 key==="2" 未遍历 -->
<li key="0" className="aa">0</li>
<li key="1" className="bb">1</li>
<li key="2" className="cc">2</li>
<!-- 之后 情况3 —— newChildren遍历完，oldFiber没遍历完 -->
<!-- oldFiber剩下 key==="1" 未遍历 -->
<li key="0" className="aa">0</li>以上就是第一轮的遍历思路，也就是处理所有可服用的节点更新情况，当然如果newChildren与oldFiber同时遍历完，就不会有下面的那些情况分析了
那么剩下的新增、删除、移动呢？ 他们都是在第二轮遍历中完成的
第二轮遍历
在第二轮遍历中依次分析下这些情况
newChildren没遍历完，oldFiber遍历完
已有的DOM节点都复用了，这时还有新加入的节点，意味着本次更新有新节点插入，我们只需要遍历剩下的newChildren为生成的workInProgress fiber依次标记Placement。
newChildren遍历完，oldFiber没遍历完
意味着本次更新比之前的节点数量少，有节点被删除了。所以需要遍历剩下的oldFiber，依次标记Deletion。
新增和删除都是挺好理解的，最难的一部分也就是节点的移动，这一部分也是大多数人不去注意的地方，当我们了解了这一部分原理，就可以在写代码的时候避免一些没必要的损耗
处理移动的节点
由于有节点改变了位置，所以不能再用位置索引i对比前后的节点，那么如何才能将同一个节点在两次更新中对应上呢？
我们需要使用key。
为了快速的找到key对应的oldFiber，我们将所有还未处理的oldFiber存入以key为key，oldFiber为value的Map中。
js
const existingChildren = mapRemainingChildren(returnFiber, oldFiber);接下来遍历剩余的newChildren，通过newChildren[i].key就能在existingChildren中找到key相同的oldFiber。
标记节点是否移动
既然我们的目标是寻找移动的节点，那么我们需要明确：节点是否移动是以什么为参照物？
我们的参照物是：最后一个可复用的节点在oldFiber中的位置索引（用变量lastPlacedIndex表示）。
由于本次更新中节点是按newChildren的顺序排列。在遍历newChildren过程中，每个遍历到的可复用节点一定是当前遍历到的所有可复用节点中最靠右的那个，即一定在lastPlacedIndex对应的可复用的节点在本次更新中位置的后面。
那么我们只需要比较遍历到的可复用节点在上次更新时是否也在lastPlacedIndex对应的oldFiber后面，就能知道两次更新中这两个节点的相对位置改变没有。
我们用变量oldIndex表示遍历到的可复用节点在oldFiber中的位置索引。如果oldIndex < lastPlacedIndex，代表本次更新该节点需要向右移动。
lastPlacedIndex初始为0，每遍历一个可复用的节点，如果oldIndex >= lastPlacedIndex，则lastPlacedIndex = oldIndex
手动狗头，文字描述看不太懂，其实看到很多博客都是制造一个动画去解释的，动画有点复杂，我们通过举例子去说明下
第一个例子
text
// 之前
abcd
// 之后
acdb
===第一轮遍历开始===
a（之后）vs a（之前）
key不变，可复用
此时 a 对应的oldFiber（之前的a）在之前的数组（abcd）中索引为0
所以 lastPlacedIndex = 0;
继续第一轮遍历...
c（之后）vs b（之前）
key改变，不能复用，跳出第一轮遍历
此时 lastPlacedIndex === 0;
===第一轮遍历结束===
===第二轮遍历开始===
newChildren === cdb，没用完，不需要执行删除旧节点
oldFiber === bcd，没用完，不需要执行插入新节点
将剩余oldFiber（bcd）保存为map
// 当前oldFiber：bcd
// 当前newChildren：cdb
继续遍历剩余newChildren
key === c 在 oldFiber中存在
const oldIndex = c（之前）.index;
此时 oldIndex === 2; // 之前节点为 abcd，所以c.index === 2
比较 oldIndex 与 lastPlacedIndex;
如果 oldIndex >= lastPlacedIndex 代表该可复用节点不需要移动
并将 lastPlacedIndex = oldIndex;
如果 oldIndex < lastplacedIndex 该可复用节点之前插入的位置索引小于这次更新需要插入的位置索引，代表该节点需要向右移动
在例子中，oldIndex 2 > lastPlacedIndex 0，
则 lastPlacedIndex = 2;
c节点位置不变
继续遍历剩余newChildren
// 当前oldFiber：bd
// 当前newChildren：db
key === d 在 oldFiber中存在
const oldIndex = d（之前）.index;
oldIndex 3 > lastPlacedIndex 2 // 之前节点为 abcd，所以d.index === 3
则 lastPlacedIndex = 3;
d节点位置不变
继续遍历剩余newChildren
// 当前oldFiber：b
// 当前newChildren：b
key === b 在 oldFiber中存在
const oldIndex = b（之前）.index;
oldIndex 1 < lastPlacedIndex 3 // 之前节点为 abcd，所以b.index === 1
则 b节点需要向右移动
===第二轮遍历结束===
最终acd 3个节点都没有移动，b节点被标记为移动第二个例子
text
// 之前
abcd
// 之后
dabc
===第一轮遍历开始===
d（之后）vs a（之前）
key改变，不能复用，跳出遍历
===第一轮遍历结束===
===第二轮遍历开始===
newChildren === dabc，没用完，不需要执行删除旧节点
oldFiber === abcd，没用完，不需要执行插入新节点
将剩余oldFiber（abcd）保存为map
继续遍历剩余newChildren
// 当前oldFiber：abcd
// 当前newChildren dabc
key === d 在 oldFiber中存在
const oldIndex = d（之前）.index;
此时 oldIndex === 3; // 之前节点为 abcd，所以d.index === 3
比较 oldIndex 与 lastPlacedIndex;
oldIndex 3 > lastPlacedIndex 0
则 lastPlacedIndex = 3;
d节点位置不变
继续遍历剩余newChildren
// 当前oldFiber：abc
// 当前newChildren abc
key === a 在 oldFiber中存在
const oldIndex = a（之前）.index; // 之前节点为 abcd，所以a.index === 0
此时 oldIndex === 0;
比较 oldIndex 与 lastPlacedIndex;
oldIndex 0 < lastPlacedIndex 3
则 a节点需要向右移动
继续遍历剩余newChildren
// 当前oldFiber：bc
// 当前newChildren bc
key === b 在 oldFiber中存在
const oldIndex = b（之前）.index; // 之前节点为 abcd，所以b.index === 1
此时 oldIndex === 1;
比较 oldIndex 与 lastPlacedIndex;
oldIndex 1 < lastPlacedIndex 3
则 b节点需要向右移动
继续遍历剩余newChildren
// 当前oldFiber：c
// 当前newChildren c
key === c 在 oldFiber中存在
const oldIndex = c（之前）.index; // 之前节点为 abcd，所以c.index === 2
此时 oldIndex === 2;
比较 oldIndex 与 lastPlacedIndex;
oldIndex 2 < lastPlacedIndex 3
则 c节点需要向右移动
===第二轮遍历结束===可以看到，我们以为从 abcd 变为 dabc，只需要将d移动到前面。
但实际上React保持d不变，将abc分别移动到了d的后面。
从这点可以看出，考虑性能，我们要尽量减少将节点从后面移动到前面的操作。