React中的神奇算法:提升组件树更新效率的秘密
这篇文章介绍了React中的diff算法的实现原理。它涵盖了单节点diff和多节点diff两种情况。单节点diff主要是通过比较key和type来判断是否复用已有的fiber节点,如果无法复用,则创建新的fiber节点。多节点diff则处理更新、新增和删除的情况,通过遍历比较新旧节点来确定复用或创建新节点,并处理节点的移动。关键方法包括updateSlot和placeChild。通过这些算法,React能够高效地更新组件树.
Prerequisite
- 下面都以
FC
为例子进行说明 - react中的diff算法的本质: 根据
current fiber
和新的ReactElement
, 生成新fiber
的过程
新的ReactElement
:renderWithHooks
中调用Component
返回的ReactElement
新fiber
: 根据新的ReactElement
创建的fiber
或者 通过useFiber
进行复用的fiber
- 复用fiber指的是
复用 current fiber 以及 对应的真实DOM节点
ReactElement
通过索引
进行访问,而current fiber
则通过fiber.sibling
.
- react中fiber节点可复用的条件:
key 和 type(元素类型) 相同
key
: 暗示哪些子元素在不同的render下能保持稳定.type
:fiber.elementType === element.type
- react中diff算法开始于
reconciler阶段
中的reconcileChildFibers
, 根据新的reactElement
(nextChild
) 的类型判断走何种 diff算法
- 单节点diff:
newChild
类型为object
、number
、string
- 多节点diff:
newChild
类型为array
// 根据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(reconcileSingleElement)
- 单节点diff 其实很简单 就是
ReactElement
在同级的current fiber
中找可复用fiber
的过程,如果找不到就创建新的fiber
. 其核心源码如下,请根据注释阅读.
- 注意下面的代码忽略了 处理
React.Lazy
以及React.Fragment
// element: new ReactElement
// currentFirstChild: retureFiber的第一个子fiber
function reconcileSingleElement(returnFiber, currentFirstChild, element, lanes) {
// 获取 element 的 key
var key = element.key;
var child = currentFirstChild;
// 遍历同级的 current fiber
while (child !== null) {
// 复用条件1: key相同
if (child.key === key) {
var elementType = element.type;
// 复用条件2: type相同
if (child.elementType === elementType) {
// 删除同级剩余的fiber节点
deleteRemainingChildren(returnFiber, child.sibling);
// 复用当前的fiber节点
var _existing = useFiber(child, element.props);
_existing.ref = coerceRef(returnFiber, child, element);
_existing.return = returnFiber;
// _existing 进入 beginWork
return _existing;
}
}
// 如果 key相同,type不同.则直接删除所有的同级fiber节点.说明没有可复用的fiber节点,直接跳出循环
deleteRemainingChildren(returnFiber, child);
break;
} else {
// key如果不相同,直接将当前fiber标记为删除
deleteChild(returnFiber, child);
}
// 继续看下一个兄弟能不能复用
child = child.sibling;
}
// 代码走到这里说明,没有找到可以复用的fiber节点.
// 则根据 ReactElement创建新的fiber节点并返回
var _created4 = createFiberFromElement(element, returnFiber.mode, lanes);
return _created4;
}
多节点diff (reconcileChildrenArray)
- 多节点diff可以分为下面主要分下面3个阶段
- 处理
更新
的情况 - 处理
新增和删除
的情况
- 新增:
oldFiber
已经遍历完, 但是newChild
还没, 说明newChild
剩下的节点都是新增节点. - 删除:
newChild
已经遍历完, 但是oldFiber
还没, 说明oldFiber
剩下的节点都需要删除.
- 处理
移动
的情况
// 多节点 diff 算法
// currentFirstChild: current fiber tree 上 以 returnFiber为父节点的第一个子节点
// newChildren: 调用 Component 新生成的 children
function reconcileChildrenArray(returnFiber, currentFirstChild, newChildren, lanes) {
/* 校验 newChildren 中的 key 是否合法 */
{
var knownKeys = null;
for (var i = 0; i < newChildren.length; i++) {
var child = newChildren[i];
knownKeys = warnOnInvalidKey(child, knownKeys, returnFiber);
}
}
/* 初始化后续算法所需要的变量 */
// resultingFirstChild: 记录 WIP fiber tree 上 以 returnFiber为父节点的第一个子节点
var resultingFirstChild = null;
// 上一个 挂载到 WIP fiber tree上的fiber节点(用于构建 WIP上子fiber的关系)
var previousNewFiber = null;
var oldFiber = currentFirstChild;
// 最后一个可复用oldFiber的位置索引
var lastPlacedIndex = 0;
// 遍历 newChild的索引
var newIdx = 0;
// 下一个 fiber节点
var nextOldFiber = null;
/* 处理更新的情况 */
for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
//...
}
/* 处理删除的情况 newChild遍历完 */
if (newIdx === newChildren.length) {
//...
return resultingFirstChild
}
/* 处理新增的情况 oldFiber遍历完 */
if (oldFiber === null) {
//...
return resultingFirstChild
}
/* 处理移动的情况 oldFiber和newChild 都没有遍历完 */
var existingChildren = mapRemainingChildren(returnFiber, oldFiber);
for (; newIdx < newChildren.length; newIdx++) {
//...
}
// 如果 newChildren已经遍历完毕, 则删除 existingChildren 中剩余的记录
if (shouldTrackSideEffects) {
existingChildren.forEach(function (child) {
return deleteChild(returnFiber, child);
});
}
// 返回 WIP fiber tree 的第一个子节点, 让其进入到 beginWork
return resultingFirstChild
}
- 首先来看处理
更新
的情况, 其实现其实并不复杂,就是逐个比较oldFiber
以及newChildren
看是否可复用
- 因为
oldFiber
是链表 所以其通过sibling
属性进行遍历, 而newChildren
则通过索引.
for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
// 获取下一个需要处理的oldFiber
if (oldFiber.index > newIdx) {
nextOldFiber = oldFiber;
oldFiber = null;
} else {
nextOldFiber = oldFiber.sibling;
}
// 判断 oldFiber 是否可复用,并返回可复用的 fiber
var newFiber = updateSlot(returnFiber, oldFiber, newChildren[newIdx], lanes);
if (newFiber === null) {
// 说明 oldFiber不可复用
if (oldFiber === null) {
oldFiber = nextOldFiber;
}
// 因为key不相同,而跳出一层循环.
break;
}
if (shouldTrackSideEffects) {
if (oldFiber && newFiber.alternate === null) {
// We matched the slot, but we didn't reuse the existing fiber, so we
// need to delete the existing child.
deleteChild(returnFiber, oldFiber);
}
}
// 使用 newChild 中 newIdx 来更新 newFiber 的 index属性(从而记录了fiber的位置)
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
previousNewFiber.sibling = newFiber;
}
// previousNewFiber始终指向 WIP tree上新增的fiber节点
previousNewFiber = newFiber;
// 继续处理下一个 oldFiber
oldFiber = nextOldFiber;
}
- 这里需要
重点关注
的第一个方法是updateSlot
, 该方法的返回值决定了是否跳出第一层循环
- 由此可以看出如果key不相同,则直接返回
null
,进而跳出第一层循环. - 我也不知道为啥
newChild !== object|string|number
🤔️ ?
// Update the fiber if the keys match, otherwise return null.
function updateSlot(returnFiber, oldFiber, newChild, lanes) {
// 获取 oldFiber上的key
// 注意 如果 newChild 没有设置key,则其key===null
var key = oldFiber !== null ? oldFiber.key : null;
// ...
if (typeof newChild === 'object' && newChild !== null) {
switch (newChild.$$typeof) {
// 注意 下面只需要关注 newChild为 REACT_ELEMENT_TYPE的情况
case REACT_ELEMENT_TYPE:
{
// 复用条件1: key相同
if (newChild.key === key) {
// 继续判断 type是否相同
return updateElement(returnFiber, oldFiber, newChild, lanes);
} else {
// 如果key不相同,则 返回 null
return null;
}
}
case REACT_PORTAL_TYPE:
//... 处理 portal
case REACT_LAZY_TYPE:
//... 处理 Lazy
}
}
// newChild 既不是 object|string|number
return null;
}
- 当 key相同的时候, 则继续调用
updateElement
判断type是否相同
.
function updateElement(returnFiber, current, element, lanes) {
// 获取 newChild的 element's type
var elementType = element.type;
// current存在,则说明是更新的情况
if (current !== null) {
// 复用条件2: elementType也相同,则直接复用oldFiber
if (current.elementType === elementType ) {
// Move based on index
var existing = useFiber(current, element.props);
existing.ref = coerceRef(returnFiber, current, element);
existing.return = returnFiber;
// 返回复用的fiber
return existing;
}
}
// current 不存在 或者 type不相同, 则根据 newChild创建新的fiber节点
var created = createFiberFromElement(element, returnFiber.mode, lanes);
created.ref = coerceRef(returnFiber, current, element);
created.return = returnFiber;
return created;
}
- 第二个需要
重点
关注的是placeChild
, 这个方法使用来更新lastPlacedIndex(最后一个可复用oldFiber的位置索引)
- 注意在
useFiber(复用oldFiber)
的方法中, 会建立newFiber
和oldFiber
的通告 alternate相互引用的关系.
workInProgress.alternate = current;
current.alternate = workInProgress;
- 还需要明白一点 newChild 每一项位置对应着
WIP fiber tree
最终的位置.
function placeChild(newFiber, lastPlacedIndex, newIndex) {
// 更新 fiber.index属性
newFiber.index = newIndex;
var current = newFiber.alternate;
// 🚀 🚀
if (current !== null) {
// current在 currentFiberTree上的位置
var oldIndex = current.index;
// 如果小于 lastPlacedIndex,则说明是移动操作
// 因为 current 在 currentFiberTree上的位置是在lastPlacedIndex的左边
// 而 newFiber 在lastPlacedIndex的右边
if (oldIndex < lastPlacedIndex) {
// This is a move.
newFiber.flags |= Placement;
// 相对顺序发生了变化
return lastPlacedIndex;
} else {
// This item can stay in place.
// oldIndex >= lastPlacedIndex 节点位置不变,并更新最近一个复用节点的位置为 lastPlacedIndex
// 如果 oldIndex>= lastPlacedIndex,则说明 current 在 currentFiberTree 上的位置是在lastPlacedIndex的右边.
// 而 newChild 代表 WIP fiber tree的最终顺序,newFiber也是在current之前,因此其相对顺序是没有改变的.
return oldIndex;
}
} else {
// This is an insertion.
newFiber.flags |= Placement;
return lastPlacedIndex;
}
}
- 接下来看
删除
和新增
的情况.
- 首先来看看
删除
, 其实现也很简单就是当newChildren已经遍历完毕了,说明 current fiber tree 中 剩余的节点都需要进行删除
if (newIdx === newChildren.length) {
// 删除 current上 未遍历到的oldFiber
deleteRemainingChildren(returnFiber, oldFiber);
// 返回 WIP fiber tree 的第一个子节点, 让其进入到 beginWork
return resultingFirstChild;
}
- 再来看看
新增
, 同样很简单它和删除
很相似,不过其是当oldFiber
遍历完,而newChildren
未遍历完. 而未遍历的newChild
则需要创建新的fiber节点
// current fiber tree上的节点已经遍历完毕了,说明 newChildren 中剩余的节点都需要进行插入
if (oldFiber === null) {
// If we don't have any more existing children we can choose a fast path
// since the rest will all be insertions.
for (; newIdx < newChildren.length; newIdx++) {
// 创建新的fiber节点
var _newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
if (_newFiber === null) {
continue;
}
// placeChild在这里的作用其实是更新newFiber.index属性
// 因为在这个使用会命中 新插入的逻辑,其不会更新 lastPlacedIndex
lastPlacedIndex = placeChild(_newFiber, lastPlacedIndex, newIdx);
// 下面的逻辑同 第一轮循环中的逻辑
if (previousNewFiber === null) {
resultingFirstChild = _newFiber;
} else {
previousNewFiber.sibling = _newFiber;
}
previousNewFiber = _newFiber;
}
// resultingFirstChild: 返回 WIP fiber
return resultingFirstChild;
}
- 最后就是处理节点移动的情况了,这个时候
newChildren
和oldFiber
都没有遍历完. 这里主要涉及到两个重要的方法一个是
mapRemainingChildren
: 这个方法的功能很简单,就是建立一个存储剩余oldFiber
的map
fiber.key | fiber.index -> fiber
function mapRemainingChildren(returnFiber, currentFirstChild) {
// Add the remaining children to a temporary map so that we can find them by
// keys quickly. Implicit (null) keys get added to this set with their index
// instead.
var existingChildren = new Map();
var existingChild = currentFirstChild;
while (existingChild !== null) {
// 存在key,则使用key作为map的键
if (existingChild.key !== null) {
existingChildren.set(existingChild.key, existingChild);
} else {
// 否则使用 fiber的index
existingChildren.set(existingChild.index, existingChild);
}
existingChild = existingChild.sibling;
}
return existingChildren;
}
updateFromMap
: 这个方法功能也很简单,就是尝试在mapRemainingChildren's map
中根据element.key | element.index
查找可复用fiber.
- 这个方法与上述的
updateSlot
有些相似, 只不过该方法始终会返回一个newFiber
,其可能是新创建的也可能是复用的.
// 从 oldFiber中寻找和 newChild key相同的fiber
// existingChildren 为 key-> oldFiber 的map
function updateFromMap(existingChildren, returnFiber, newIdx, newChild, lanes) {
if (typeof newChild === 'string' || typeof newChild === 'number') {
// 处理 textNode
var matchedFiber = existingChildren.get(newIdx) || null;
return updateTextNode(returnFiber, matchedFiber, '' + newChild, lanes);
}
if (typeof newChild === 'object' && newChild !== null) {
switch (newChild.$$typeof) {
case REACT_ELEMENT_TYPE:
{
// 优先使用 key 来查找,如果没有key,则使用index
var _matchedFiber = existingChildren.get(newChild.key === null ? newIdx : newChild.key) || null;
// 如果 _matchedFiber存在,则继续判断 type 是否相同,如果相同则复用_matchedFiber
// 不存在或者type 不相同,则创建新的fiber
return updateElement(returnFiber, _matchedFiber, newChild, lanes);
}
case REACT_PORTAL_TYPE:
//...处理 Portal
case REACT_LAZY_TYPE:
//...处理 Lazy
}
return null;
}
- ok了解了上述两个方法之后,再看下面这段逻辑就简单了.
// 走到了这里说明 current fiber tree 和 newChildren 中都还有剩余的节点.
var existingChildren = mapRemainingChildren(returnFiber, oldFiber); // Keep scanning and use the map to restore deleted items as moves.
for (; newIdx < newChildren.length; newIdx++) {
var _newFiber2 = updateFromMap(existingChildren, returnFiber, newIdx, newChildren[newIdx], lanes);
if (_newFiber2 !== null) {
if (shouldTrackSideEffects) {
if (_newFiber2.alternate !== null) {
// 已经找到了可复用的oldFiber,则删除 map中的记录
existingChildren.delete(_newFiber2.key === null ? newIdx : _newFiber2.key);
}
}
// 更新 lastPlacedIndex 为最新复用fiber的index
lastPlacedIndex = placeChild(_newFiber2, lastPlacedIndex, newIdx);
// 同上
if (previousNewFiber === null) {
resultingFirstChild = _newFiber2;
} else {
previousNewFiber.sibling = _newFiber2;
}
previousNewFiber = _newFiber2;
}
}
转载自:https://juejin.cn/post/7245567988249182245