【React 18.2 源码学习】diff 算法包会——从手撸到源码
前置文章：React render 原来你是这样的
diff 过程入口
beginWork 会根据当前节点具体类型，进入对应的处理流程，在这些流程中最终都会执行 reconcileChildren， reconcileChildren 就是在 beginWork 中开始生成下一级 FiberNode 的入口函数，是协调（reconcile） 开始的地方，协调的过程也就是 React 中的 diff 过程。
可以看到初次渲染的时候执行了 mountChildFibers 方法，更新的时候执行了 reconcileChildFibers，但其实这两个方法是同一个方法，只是接收的参数不一样。接着看下两个方法的定义：
可以看到这两方法都是执行 ChildReconciler 得来的，区别就是参数 shouldTrackSideEffects 一个为 true 一个为 false。shouldTrackSideEffects 的意思为是否在协调的时候标记副作用。
为什么初次渲染的时候 shouldTrackSideEffects 为 false 。
答案是为了初次渲染能有更好的性能。因为如果初次渲染也要标记副作用的话，会有很多的节点被标记为 Placement （新增节点），在 commit 阶段会依据副作用频繁操作 DOM （每个父 DOM 都会进行一次添加子 DOM 的操作），而不标记副作用时，因为根节点一直都存在，所以根节点是更新并会被标记 Placement，而其他节点会在 beginWork 阶段构建一棵离屏的 DOM 树，最终在 commit 阶段只需要根节点将 DOM 树一次性添加到页面即可。
reconcile（diff） 算法解析
在 React 中，即使在最前沿的算法中，该算法的复杂程度为O(n3)，其中 n 是树中元素的数量。如果在 React 中使⽤了该算法，那么展示 1000 个元素所需要执⾏的计算 量将在⼗亿的量级范围。这个开销实在是太过⾼昂。于是 React 基于以下三个条件将复杂度降低到了 O(n)。 1、只对同级元素进行 Diff。如果一个 DOM 元素更新前后跨越了层级，则不会复用。 2、两个不同类型的元素会产生不同的树。比如更新前是 p ，更新后是 div 则不会复用。 3、开发者可以通过 key prop 来暗示哪些⼦元素在不同的渲染下能保持稳定
在实践中发现以上条件在⼏乎所有实⽤的场景下都成立。 下面从以下两种情况来看看 reconcile 算法具体是怎样的：
- 单节点 reconcile
- 多节点 reconcile
注意： 下面提到的老节点都是指的老的FiberNode，新节点指的是 React 元素（因为此时新节点还未生成Fiber，diff 的过程也是生成新节点对应的 FiberNode 的过程），不清楚 FiberNode 和 React 元素区别的可以看看我的JSX 竟然是 Fiber 的爷爷 这篇文章
单节点 reconcile(diff)
下面是单节点 reconcile 的流程图。
单节点 reconcile 是指新的节点只有一个，那为什么流程图中要进行遍历循环呢，这是因为虽然新的节点只有一个，但是之前的节点可能不止一个，所以要对老的节点进行循环，然后用遍历到的老节点和新的节点比较（同级比较）：
- 如果老节点和新节点的 key 相同，就继续判断 type ，如果也相同，那么这个节点就可以进行复用，然后返回这个复用的节点，并把其他节点标记为删除，然后结束当前的 reconcile 流程。
- 如果 type 不相同，则说明当前节点的类型发生了变化（比如从 p 变成了div），需要重新生成，剩下的节点全部标记删除，并结束当前的 reconcile 流程。（对应条件二）
- 如果老节点和新节点的 key 不相同，标记老节点删除，继续遍历。
- 如果遍历结束也没有找到和新节点 key 相同的老节点，那么就会重新生成节点，结束当前的 reconcile 流程。
下面手撸一个丐版单节点 diff
function cloneFiber(old, new){
return {
...oldFiber,
...newFiber
}
}
function Fiber(old, new){
return {...new }
}
function reconcileSingleElement(oldArr, newChild) {
const result = null;
for(let i =0; i < oldArr.length; i++) {
const oldchild = oldArr[i];
if(oldchild.key === newChild.key) {
if(oldchild.key === newChild.key) {
// 复用
result = cloneFiber(oldchild,newchild)
}else {
//不能复用删除剩下的节点并 跳出循环
break
}
}
}
// 新生成节点
result = new Fiber(newChild);
return result
}
多节点 reconcile(diff)
多节点的情况比单节点要复杂的多，主要分为以下几个情况：
- 节点不变（可能节点内容会存在更新）
- 节点增加或者删除
- 节点移动
那针对上面的情况，diff 的算法设计思路是：
- 判断当前节点属于哪种情况
- 如果是增删，执行增删逻辑
- 如果位置不变，执行相应更新逻辑
- 如果是移动，执行移动逻辑 因为在日常开发中，‘节点移动’的情况会比较少（反正我目前还没咋遇到过），因此在优先级相同的情况下， diff 算法会优先处理另外两个情况。基于以上信息，diff 算法会经历两轮遍历：
- 第一轮尝试尽可能的按顺序复用节点
- 第二轮遍历处理剩下的节点。当然也有例外，对于位置不变的情况下，只需要进行第一轮遍历。
下面是多节点的流程图
第一轮遍历
首先来看第一轮遍历，当新老节点 key 不相同的跳出第一轮循环，当新老节点key相同时继续循环，分为两种情况，一种是新老节点 type 相同，此时节点可以复用。另一种情况是 type 不同，此时节点不能复用，需要生成新的节点同时给老节点标记删除。不管 type 是否相同都会更新最后一个被复用节点的索引（这个索引被用来判断节点是否发生移动）。如果正常循环退出时，老节点和新节点都遍历完成，则不需要进入第二轮遍历，diff 结束。
第二轮遍历
第二轮遍历分为几种情况： 第一种新节点在第一轮遍历完了，旧节点没遍历完，新少旧多说明有删除的节点，第二轮遍历需要删除剩余的老节点。 第二种是新节点没遍历完，但是旧节点遍历完了，旧少新多说明有新增的节点，第二轮遍历需要创建新节点并打上新增的标记
第三种是新老节点都没遍历完，说明发生了移动，第二轮遍历需要处理移动。为了查找的效率，需要将老节点以 key 为索引存在 map 中，通过遍历新节点同时根据新节点的 key 找出可以复用的老节点，如果找到则把 map 中对应的老节点删除，然后根据最后一个被复用的节点的位置确定当前节点是否移动。遍历结束后将 map 中的节点全部标记删除
如何判断节点移动
根据 lastPlacedIndex （最后一个可复用的节点的位置索引，这个对应的是老节点的位置索引）来判断。因为新节点中的节点顺序代表了更新后的节点顺序，如果新节点能找到相同 key 对应的老节点，那么会有两种情况： 1、oldFiber.index < lastPlacedIndex 说明 oldFIber 在 lastPlacedIndex 对应的老节点左边，也就是原来这个节点在 lastPlacedIndex 对应节点的左边，但是当前的新节点一定在 lastPlacedIndex 对应的新节点的右边（因为新节点的顺序就是更新后的节点顺序，因此后遍历的节点会在先遍历的节点的右边），因此当前的新 FIberNode 发生了移动 2、oldFiber.index >= lastPlacedIndex 说明 oldFIber 在 lastPlacedIndex 对应的节点右边，与新节点当前位置一致，所以没有发生移动，同时更新 lastPlacedIndex 的值为 oldFiber.index
举个例子
需要注意的是，在开发中要尽量避免将后面的节点移动到前面，因为这会导致性能不好，可以看下面的例子
手撸多节点 diff
下面我们来利用上面的策略实现一个丐版的 diff 算法： 主要功能是 diff 两个数组对象，并标记出新旧数组对象的变化；
/*
入参：[]{
key:1,
type: 'div'
},
*/
function cloneFiber(old, new){
return {
...oldFiber,
...newFiber
}
}
function Fiber(old, new){
return {...new }
}
function reconcileArray(
oldArray,
newArray,
){
// diff 结果存放数组
const resultArr = [];
// 最后一个复用的位置
let lastPlacedIndex = 0;
// 遍历新数组对象的索引
let newIdx = 0;
// 遍历旧数组对象的索引
let oldIdx = 0;
// 第一轮遍历
for (; oldIdx < oldArray.length && newIdx < newArray.length; newIdx++, oldIdx++) {
const oldItem = oldArray[oldIdx];
const newItem = newArray[newIdx];
let resultItem = null;
if(oldItem.key === newItem.key) {
if(oldItem.type === newItem.type) {
// key 和 type 都相同 复用
resultItem = cloneFiber(oldItem, newItem);
} else {
// key 相同，type 不相同生成一个新的节点
resultItem = new Fiber(newItem);
// 原来的节点删除
oldItem.flag = 'Deletion';
resultArr.push(oldItem);
}
} else {
// key 不相同跳出第一轮循环
break;
}
// 更新最后一个复用的位置，并标记对应的副作用
lastPlacedIndex = placeChild(oldArray, newItem, lastPlacedIndex);
resultArr.push(newItem)
}
if (newIdx === newArray.length) {
// 说明新节点已经遍历完了，需要给剩下的老节点标记删除
for(; oldIdx < oldArray.length; oldIdx++) {
const oldItem = oldArray[oldIdx]
oldItem.flag = 'Deletion';
resultArr.push(oldItem);
}
// diff结束
return resultArr;
}
if (oldIdx === oldArray.length) {
// 旧节点已经全部遍历完了，新节点还有，对剩下的新节点标记更新
for(; newIdx < newArray.length; newIdx++) {
const newItem = newArray[newIdx]
newItem.flag = 'Placement';
resultArr.push(newItem);
}
// diff 结束
return resultArr;
}
// 将剩下的老节点用key值存储到 map 中方便快速查找
const existingChildren = mapRemainingChildren(oldArray, oldIdx);
// 对剩下的新节点进行遍历，并对老节点尽可能的复用
for (; newIdx < newArray.length; newIdx++) {
const newItem = newArray[newIdx];
// 根据 key 获取对应的老节点
const oldItem = existingChildren.get(newItem.key || newIdx);
let resultItem = null;
if(oldItem) {
// 找到了对应的老节点
if(oldItem.key === newItem.key) {
if(oldItem.type === newItem.type) {
// key 和 type 都相同 复用
resultItem = cloneFiber(oldItem, newItem);
} else {
// key 相同，type 不相同生成一个新的节点
resultItem = new Fiber(newItem);
// 原来的节点删除
oldItem.flag = 'Deletion';
resultArr.push(oldItem);
}
}
// 将 map 中对应的老节点删除
existingChildren.delete(newItem.key || newIdx);
} else{
// 没找到对应的老节点 生成新节点
resultItem = {...newItem};
}
// 更新最后一个复用的位置，并标记对应的副作用
lastPlacedIndex = placeChild(oldArray, resultItem, lastPlacedIndex);
resultArr.push(resultItem);
}
// 将 map 中剩下的节点都标记为删除
existingChildren.forEach(item => {
item.flag = 'Deletion';
resultArr.push(item);
});
return resultArr;
}
function placeChild(oldArray, newItem,lastPlacedIndex) {
// 这里是替代 react 中取老节点的index
const oldIdx = oldArray.findIndex(item => newItem.key === item.key);
if(oldIdx < 0) {
// 没有找到对应的老节点,说明是新增
newItem.flag = 'Placement';
} else {
// 找到了老节点
if(oldIdx < lastPlacedIndex) {
// 说明移动了
newItem.flag = 'Placement-Move';
return lastPlacedIndex
} else {
// 没有移动,同时更新最后复用的位置
return oldIdx
}
}
}
function mapRemainingChildren(oldArr, index) {
const map = new Map();
for(let i = index; i < oldArr.length; i++) {
const item = oldArr[i];
if(item.key) {
// key 存在
map.set(item.key, item);
} else {
// key 不存在 用 index 替代 key 值
map.set(index, item)
}
}
return map;
}
const old = [
{
key:1,
type: 'div'
},
{
key:2,
type: 'div'
},
{
key:3,
type: 'div'
},
{
key:4,
type: 'div'
},
{
key:5,
type: 'div'
},
]
const newArr = [
{
key:5,
type: 'div'
},
{
key:1,
type: 'div'
},
{
key:2,
type: 'div'
},
{
key:3,
type: 'div'
},
{
key:6,
type: 'div'
},
]
const result = reconcileArray(old,newArr);
console.log(result);
上源码
前面说了 diff 的入口是 ChildReconciler，他方法内部定义了一堆方法，如下：
方法最终返回了 reconcileChildFibers 方法，也就是 diff 最终执行的就是这个方法，下面看看这个方法
placeSingleChild 主要是给单节点 diff 完成的节点标记 flag 的；
单节点 diff 根据新节点的类型分了三种情况，这里我们主要看一下 react 元素的情况也就是reconcileSingleElement
多节点 diff 分为两种，一种是数组的，一种是 Iterator 的，两种的算法一样，根据特性实现有点不一样，这里我们主要看下数组的 也就是 reconcileChildrenArray，代码有点多，截了两张图
核心的算法就是这些，下面再看看算法当中用到的一些处理方法
最后
感谢大家的阅读，有不对的地方也欢迎大家指出来。
参考资料
React设计原理-卡颂 React18.2.0源码