共计 6889 个字符，预计需要花费 18 分钟才能阅读完成。
react 源码解析 9.diff 算法
视频解说（高效学习）：进入学习
往期文章：
1. 开篇介绍和面试题
2.react 的设计理念
3.react 源码架构
4. 源码目录构造和调试
5.jsx& 外围 api
6.legacy 和 concurrent 模式入口函数
7.Fiber 架构
8.render 阶段
9.diff 算法
10.commit 阶段
11. 生命周期
12. 状态更新流程
13.hooks 源码
14. 手写 hooks
15.scheduler&Lane
16.concurrent 模式
17.context
18 事件零碎
19. 手写迷你版 react
20. 总结 & 第一章的面试题解答
21.demo
在 render 阶段更新 Fiber 节点时，咱们会调用 reconcileChildFibers 比照 current Fiber 和 jsx 对象构建 workInProgress Fiber，这里 current Fiber 是指以后 dom 对应的 fiber 树，jsx 是 class 组件 render 办法或者函数组件的返回值。
在 reconcileChildFibers 中会依据 newChild 的类型来进入单节点的 diff 或者多节点 diff
//ReactChildFiber.old.js
function reconcileChildFibers(
returnFiber: Fiber,
currentFirstChild: Fiber | null,
newChild: any,
): Fiber | null {
const isObject = typeof newChild === 'object' && newChild !== null;
if (isObject) {switch (newChild.$$typeof) {
case REACT_ELEMENT_TYPE:
// 繁多节点 diff
return placeSingleChild(
reconcileSingleElement(
returnFiber,
currentFirstChild,
newChild,
lanes,
),
);
}
}
//...
if (isArray(newChild)) {
// 多节点 diff
return reconcileChildrenArray(
returnFiber,
currentFirstChild,
newChild,
lanes,
);
}
// 删除节点
return deleteRemainingChildren(returnFiber, currentFirstChild);
}diff 过程的次要流程如下图：
咱们晓得比照两颗树的复杂度自身是 O(n3)，对咱们的利用来说这个是不能接受的量级，react 为了升高复杂度，提出了三个前提：
- 只对同级比拟，跨层级的 dom 不会进行复用
- 不同类型节点生成的 dom 树不同，此时会间接销毁老节点及子孙节点，并新建节点
-
能够通过 key 来对元素 diff 的过程提供复用的线索，例如：
const a = ( <> <p key="0">0</p> <p key="1">1</p> </> ); const b = ( <> <p key="1">1</p> <p key="0">0</p> </> );
如果 a 和 b 里的元素都没有 key，因为节点的更新前后文本节点不同，导致他们都不能复用，所以会销毁之前的节点，并新建节点，然而当初有 key 了，b 中的节点会在老的 a 中寻找 key 雷同的节点尝试复用，最初发现只是替换地位就能够实现更新，具体比照过程前面会讲到。
单节点 diff
单点 diff 有如下几种状况：
- key 和 type 雷同示意能够复用节点
- key 不同间接标记删除节点，而后新建节点
- key 雷同 type 不同，标记删除该节点和兄弟节点，而后新创建节点
function reconcileSingleElement(
returnFiber: Fiber,
currentFirstChild: Fiber | null,
element: ReactElement
): Fiber {
const key = element.key;
let child = currentFirstChild;
//child 节点不为 null 执行比照
while (child !== null) {
// 1. 比拟 key
if (child.key === key) {
// 2. 比拟 type
switch (child.tag) {
//...
default: {if (child.elementType === element.type) {
// type 雷同则能够复用 返回复用的节点
return existing;
}
// type 不同跳出
break;
}
}
//key 雷同，type 不同则把 fiber 及和兄弟 fiber 标记删除
deleteRemainingChildren(returnFiber, child);
break;
} else {
//key 不同间接标记删除该节点
deleteChild(returnFiber, child);
}
child = child.sibling;
}
// 新建新 Fiber
}多节点 diff
多节点 diff 比较复杂，咱们分三种状况进行探讨，其中 a 示意更新前的节点，b 示意更新后的节点
-
属性变动
const a = ( <> <p key="0" name='0'>0</p> <p key="1">1</p> </> ); const b = ( <> <p key="0" name='00'>0</p> <p key="1">1</p> </> );
-
type 变动
const a = ( <> <p key="0">0</p> <p key="1">1</p> </> ); const b = ( <> <div key="0">0</div> <p key="1">1</p> </> );
-
新增节点
const a = ( <> <p key="0">0</p> <p key="1">1</p> </> ); const b = ( <> <p key="0">0</p> <p key="1">1</p> <p key="2">2</p> </> );
-
节点删除
const a = ( <> <p key="0">0</p> <p key="1">1</p> <p key="2">2</p> </> ); const b = ( <> <p key="0">0</p> <p key="1">1</p> </> );
-
节点地位变动
const a = ( <> <p key="0">0</p> <p key="1">1</p> </> ); const b = ( <> <p key="1">1</p> <p key="0">0</p> </> );
在源码中多节点 diff 有三个 for 循环遍历（并不意味着所有更新都有经验三个遍历，进入循环体有条件，也有条件跳出循环），第一个遍历解决节点的更新（包含 props 更新和 type 更新和删除），第二个遍历解决其余的状况（节点新增），其起因在于在大多数的利用中，节点更新的频率更加频繁，第三个解决位节点置扭转
-
第一次遍历
因为老的节点存在于 current Fiber 中，所以它是个链表构造，还记得 Fiber 双缓存构造嘛，节点通过 child、return、sibling 连贯，而 newChildren 存在于 jsx 当中，所以遍历比照的时候，首先让 newChildren[i]` 与 `oldFiber 比照，而后让 i ++、nextOldFiber = oldFiber.sibling。在第一轮遍历中，会解决三种状况，其中第 1，2 两种状况会完结第一次循环- key 不同，第一次循环完结
- newChildren 或者 oldFiber 遍历完，第一次循环完结
- key 同 type 不同，标记 oldFiber 为 DELETION
- key 雷同 type 雷同则能够复用
newChildren 遍历完，oldFiber 没遍历完，在第一次遍历实现之后将 oldFiber 中没遍历完的节点标记为 DELETION，即删除的 DELETION Tag
-
第二个遍历
第二个遍历思考三种状况-
newChildren 和 oldFiber 都遍历完：多节点 diff 过程完结
-
newChildren 没遍历完，oldFiber 遍历完，将剩下的 newChildren 的节点标记为 Placement，即插入的 Tag
- newChildren 和 oldFiber 没遍历完，则进入节点挪动的逻辑
-
-
-
第三个遍历
次要逻辑在 placeChild 函数中，例如更新前节点程序是 ABCD，更新后是 ACDB-
newChild 中第一个地位的 A 和 oldFiber 第一个地位的 A，key 雷同可复用，lastPlacedIndex=0
- newChild 中第二个地位的 C 和 oldFiber 第二个地位的 B，key 不同跳出第一次循环，将 oldFiber 中的 BCD 保留在 map 中
- newChild 中第二个地位的 C 在 oldFiber 中的 index=2 > lastPlacedIndex= 0 不须要挪动，lastPlacedIndex=2
- newChild 中第三个地位的 D 在 oldFiber 中的 index=3 > lastPlacedIndex= 2 不须要挪动，lastPlacedIndex=3
- newChild 中第四个地位的 B 在 oldFiber 中的 index=1 < lastPlacedIndex=3, 挪动到最初
看图更直观
例如更新前节点程序是 ABCD，更新后是 DABC
-
newChild 中第一个地位的 D 和 oldFiber 第一个地位的 A，key 不雷同不可复用，将 oldFiber 中的 ABCD 保留在 map 中，lastPlacedIndex=0
- newChild 中第一个地位的 D 在 oldFiber 中的 index=3 > lastPlacedIndex= 0 不须要挪动，lastPlacedIndex=3
- newChild 中第二个地位的 A 在 oldFiber 中的 index=0 < lastPlacedIndex=3, 挪动到最初
- newChild 中第三个地位的 B 在 oldFiber 中的 index=1 < lastPlacedIndex=3, 挪动到最初
- newChild 中第四个地位的 C 在 oldFiber 中的 index=2 < lastPlacedIndex=3, 挪动到最初
看图更直观
-
代码如下：
//ReactChildFiber.old.js
function placeChild(newFiber, lastPlacedIndex, newIndex) {
newFiber.index = newIndex;
if (!shouldTrackSideEffects) {return lastPlacedIndex;}
var current = newFiber.alternate;
if (current !== null) {
var oldIndex = current.index;
if (oldIndex < lastPlacedIndex) {
//oldIndex 小于 lastPlacedIndex 的地位 则将节点插入到最初
newFiber.flags = Placement;
return lastPlacedIndex;
} else {return oldIndex;// 不须要挪动 lastPlacedIndex = oldIndex;}
} else {
// 新增插入
newFiber.flags = Placement;
return lastPlacedIndex;
}
}//ReactChildFiber.old.js
function reconcileChildrenArray(
returnFiber: Fiber,// 父 fiber 节点
currentFirstChild: Fiber | null,//childs 中第一个节点
newChildren: Array<*>,// 新节点数组 也就是 jsx 数组
lanes: Lanes,//lane 相干 第 12 章介绍
): Fiber | null {
let resultingFirstChild: Fiber | null = null;//diff 之后返回的第一个节点
let previousNewFiber: Fiber | null = null;// 新节点中上次比照过的节点
let oldFiber = currentFirstChild;// 正在比照的 oldFiber
let lastPlacedIndex = 0;// 上次可复用的节点地位 或者 oldFiber 的地位
let newIdx = 0;// 新节点中比照到了的地位
let nextOldFiber = null;// 正在比照的 oldFiber
for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {// 第一次遍历
if (oldFiber.index > newIdx) {//nextOldFiber 赋值
nextOldFiber = oldFiber;
oldFiber = null;
} else {nextOldFiber = oldFiber.sibling;}
const newFiber = updateSlot(// 更新节点，如果 key 不同则 newFiber=null
returnFiber,
oldFiber,
newChildren[newIdx],
lanes,
);
if (newFiber === null) {if (oldFiber === null) {oldFiber = nextOldFiber;}
break;// 跳出第一次遍历
}
if (shouldTrackSideEffects) {// 查看 shouldTrackSideEffects
if (oldFiber && newFiber.alternate === null) {deleteChild(returnFiber, oldFiber);
}
}
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);// 标记节点插入
if (previousNewFiber === null) {resultingFirstChild = newFiber;} else {previousNewFiber.sibling = newFiber;}
previousNewFiber = newFiber;
oldFiber = nextOldFiber;
}
if (newIdx === newChildren.length) {deleteRemainingChildren(returnFiber, oldFiber);// 将 oldFiber 中没遍历完的节点标记为 DELETION
return resultingFirstChild;
}
if (oldFiber === null) {for (; newIdx < newChildren.length; newIdx++) {// 第 2 次遍历
const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
if (newFiber === null) {continue;}
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);// 插入新增节点
if (previousNewFiber === null) {resultingFirstChild = newFiber;} else {previousNewFiber.sibling = newFiber;}
previousNewFiber = newFiber;
}
return resultingFirstChild;
}
// 将剩下的 oldFiber 退出 map 中
const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
for (; newIdx < newChildren.length; newIdx++) {// 第三次循环 解决节点挪动
const newFiber = updateFromMap(
existingChildren,
returnFiber,
newIdx,
newChildren[newIdx],
lanes,
);
if (newFiber !== null) {if (shouldTrackSideEffects) {if (newFiber.alternate !== null) {
existingChildren.delete(// 删除找到的节点
newFiber.key === null ? newIdx : newFiber.key,
);
}
}
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);// 标记为插入的逻辑
if (previousNewFiber === null) {resultingFirstChild = newFiber;} else {previousNewFiber.sibling = newFiber;}
previousNewFiber = newFiber;
}
}
if (shouldTrackSideEffects) {
// 删除 existingChildren 中剩下的节点
existingChildren.forEach(child => deleteChild(returnFiber, child));
}
return resultingFirstChild;
}
正文完
