Signal ledger / designed reading stage
Virtual DOM 和 Diff 解读
理解 Virtual DOM 和 Diff 算法
Transition band / reading fieldLong-form note2022-07-22
Continue through the ledger
理解 Virtual DOM 和 Diff 算法
Diff 算法是一套理论模型，为了查找出前一次是否有能够重复利用的节点。React 基于这种理论模型实现了一套 Diff 算法，而数据类型则是 Virtual DOM。
真正的 DOM 节点是由类似 document.createElement 生成的，而 Virtual
DOM 则是 FiberNode 类的实例组成的节点树。
React 会在更新阶段，判断 bailout 失败后进入 Diff 算法的逻辑。当处理到 A 节点时，对 A 节点的 Diff 其实是将 A 提供给 Diff 算法，并从 A.child 节点开始与新的 children 比较。
在官方文档中，简述了 React Diff 的策略：
一个 DOM 节点在某一时刻最多会有 4 个节点和他相关。
render
方法的返回结果或 FunctionComponent 的调用结果。JSX 对象中包含描述 DOM 节点的信息。Diff 算法的本质是对比 1 和 4，生成 2。
为了降低算法复杂度，React 的 Diff 算法会预设三个限制：
只对同级兄弟元素进行 Diff。
如果一个 DOM 节点在更新中跨越了层级，那么 React 认为变动节点的旧节点需要删除，不会尝试复用。
两个不同类型的标签会产生出不同的节点树。
如果元素由 div 变为 p，React 会销毁 div 及其子孙节点，并新建 p 及其子孙节点。
通过 key 来标记。
通常用于表明元素在同层级的类似元素中各自 key，用于发生同层级移动时的查找。
Diff 获取到 fiber.child 并根据 typeof 返回的类型，如 object(array)、string 做不同处理。
function reconcileChildFibers(
returnFiber: Fiber, // 父节点
currentFirstChild: Fiber | null, // 当前父节点下的第一个 child
newChild: any, // 即将更新的 children ，由jsx决定，如果是一个单节点则是object 如果是多个节点并列则是 Array<object
lanes: Lanes,
): Fiber | null {
if (typeof newChild === 'object' && newChild !== null) {
switch (newChild.$$typeof) {
case REACT_ELEMENT_TYPE:
return placeSingleChild(
reconcileSingleElement(returnFiber, currentFirstChild, newChild, lanes),
)
// ...
}
if (isArray(newChild)) {
return reconcileChildrenArray(returnFiber, currentFirstChild, newChild, lanes)
}
if (getIteratorFn(newChild)) {
return reconcileChildrenIterator(returnFiber, currentFirstChild, newChild, lanes)
}
}
if ((typeof newChild === 'string' && newChild !== '') || typeof newChild === 'number') {
return placeSingleChild(
reconcileSingleTextNode(returnFiber, currentFirstChild, '' + newChild, lanes),
)
}
return deleteRemainingChildren(returnFiber, currentFirstChild)
}如果节点内仅有 string/number，如
return 'text'。如果有 oldChild 类型相同都是文字节点的话，则都可以复用。
function reconcileSingleTextNode(
returnFiber: Fiber,
currentFirstChild: Fiber | null,
textContent: string,
lanes: Lanes,
): Fiber {
if (currentFirstChild !== null && currentFirstChild.tag === HostText) {
deleteRemainingChildren(returnFiber, currentFirstChild.sibling)
const existing = useFiber(currentFirstChild, textContent)
existing.return = returnFiber
return existing
}
deleteRemainingChildren(returnFiber, currentFirstChild)
const created = createFiberFromText(textContent, returnFiber.mode, lanes)
created.return = returnFiber
return created
}function reconcileSingleElement(
returnFiber: Fiber,
currentFirstChild: Fiber | null,
element: ReactElement,
lanes: Lanes,
): Fiber {
const key = element.key
let child = currentFirstChild
while (child !== null) {
if (child.key === key) {
const elementType = element.type
if (child.elementType === elementType) {
deleteRemainingChildren(returnFiber, child.sibling)
const existing = useFiber(child, element.props)
existing.ref = coerceRef(returnFiber, child, element)
existing.return = returnFiber
return existing
}
deleteRemainingChildren(returnFiber, child)
break
} else {
deleteChild(returnFiber, child)
}
child = child.sibling
}
const created = createFiberFromElement(element, returnFiber.mode, lanes)
created.ref = coerceRef(returnFiber, currentFirstChild, element)
created.return = returnFiber
return created
}当新节点的类型是 object 时，该节点只能是
ReactElement，ReactPortal,ReactLazyElement类型。拿常见的 ReactElement 举例来看吧。
从代码可以看出，React 通过先判断 key 是否相同（没有赋值的 key 值为 null）
key 相同且 type 相同时，可以复用。key 相同但 type 不同时，无法复用。key 不同，说明还没找到对应的 oldChild，删除当前不符合的 oldChild
继续查找剩下的兄弟节点。因为是单个节点 diff，当查找到可以复用的节点时，意味着剩下的兄弟节点都应当删除（如果不删除则意味着 newChild 应该是 array 数据类型）。通过
deleteRemainingChildren 删除多余的 sibling 节点。
如果是 array，会进入 reconcileChildrenArray 的逻辑。
对于同级数组节点的变化有以下几种可能性：
key没有变化，其他属性有更新，执行更新逻辑在 React 的实现中，会先开始一次对新 children 的遍历，优先处理节点更新的逻辑。将 newIdx 递增并检查 newChild 是否有可以利用的 oldChild，如果有则利用并将 oldChild 更新。
let resultingFirstChild: Fiber | null = null // 返回 作为 return 的 child 属性(first child)
let previousNewFiber: Fiber | null = null // 中间变量连接上一个 newFiber 和 当前的 newFiber
let oldFiber = currentFirstChild
let lastPlacedIndex = 0 // 本次更新的 fiber 对应的 dom 需要插入的位置
let newIdx = 0 // newChildren 已经处理到哪个位置了
let nextOldFiber = null // 下一个供比对的 oldFiber
for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
if (oldFiber.index > newIdx) {
nextOldFiber = oldFiber
oldFiber = null
} else {
nextOldFiber = oldFiber.sibling
}
// updateSlot 比较 oldFiber 和 newChild 的 key 是否相等，相等的话可以复用，不相等的话返回 null。
const newFiber = updateSlot(returnFiber, oldFiber, newChildren[newIdx], lanes)
// 由于 key 不同，不可复用，会跳出第一次循环
if (newFiber === null) {
if (oldFiber === null) {
oldFiber = nextOldFiber
}
break
}
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx) //
if (previousNewFiber === null) {
resultingFirstChild = newFiber
} else {
previousNewFiber.sibling = newFiber
}
previousNewFiber = newFiber
oldFiber = nextOldFiber
}
function placeChild(newFiber: Fiber, lastPlacedIndex: number, newIndex: number): number {
newFiber.index = newIndex
if (!shouldTrackSideEffects) {
return lastPlacedIndex
}
// newFiber 的 旧节点
const current = newFiber.alternate
if (current !== null) {
const oldIndex = current.index // abcd -> acdb
if (oldIndex < lastPlacedIndex) {
newFiber.flags |= Placement
return lastPlacedIndex
} else {
// 当 newFibber 的新位置序号大于旧位置，则不需要移动
return oldIndex
}
} else {
newFiber.flags |= Placement
return lastPlacedIndex
}
}从
placeChild方法可以看出，减少将节点从后面移动到前面的操作可以提高性能。
第一次遍历的结束条件是：
当第一次遍历完成后有下列三种情况：
oldChildren 和 newChildren 都遍历完成，这种情况下认为 Diff 已经完成
oldChildren 或 newChildren 之一遍历完成
这种情况下，如果还剩下 oldChildren ，则将剩下的 oldChild 都删除。
如果剩下 newChildren，则遍历剩余的 newChild 并创建新的 fiber，连接到第一次遍历结束的末尾
// newChildren 遍历完成
if (newIdx === newChildren.length) {
deleteRemainingChildren(returnFiber, oldFiber)
return resultingFirstChild
}
// oldChildren 遍历完成
if (oldFiber === null) {
for (; newIdx < newChildren.length; newIdx++) {
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
}oldChildren 和 newChildren 都没有遍历完成，意味着 oldChildren 没有遍历完成，其中仍有可能可以利用的节点。
// 将链表结构的 oldChildren 转化成 Map 的映射结构
const existingChildren = mapRemainingChildren(returnFiber, oldFiber)
for (; newIdx < newChildren.length; newIdx++) {
// 构建 newFiber, 在 existingChildren 查找是否能有复用的 fiber。如果有则复用，没有则创建新 fiber
const newFiber = updateFromMap(
existingChildren,
returnFiber,
newIdx,
newChildren[newIdx],
lanes
)
if (newFiber !== null) {
if (shouldTrackSideEffects) {
// 有 alternate 意味着是通过复用生成的
if (newFiber.alternate !== null) {
// 删除对应的 oldChild
existingChildren.delete(
newFiber.key === null ? newIdx : newFiber.key
)
}
}
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx)
// 如果 previousNewFiber 为 null 说明第一个循环的第一个节点就跳出循环，需要设置 firstFiber
if (previousNewFiber === null) {
resultingFirstChild = newFiber
} else {
previousNewFiber.sibling = newFiber // 将 newFiber 接在上一个 newFiber 的 sibling 属性
}
previousNewFiber = newFiber // 更新 previousNewFiber
}
// 删除剩余没用的 oldChild
if (shouldTrackSideEffects) {
existingChildren.forEach(child => deleteChild(returnFiber, child))
}
return resultingFirstChild这种是最复杂的情况。意味着剩余的 oldChildren 中仍有可能提供给剩余 newChildren 复用的 fiber
将 oldChildren 以 key/index 做键，fiber 做值，生成 Map 类型的 existingChildren。
再遍历剩下的 newChildren，对比如果发现可以复用则可以添加到
lastPlacedIndex，只需要比较找到的可复用 oldFiber 在更新前是否也在 lastPlacedIndex 对应的
oldFiber 后面，就能知道两次更新中这两个节点的相对位置改变没有。
abcd -> acdb // 遍历新 children， a-c-d 标记不用改变 到 b 时标记移动
abcd -> dabc // 遍历新 children, d 标记不用改变， a-b-c 标记移动如果前后顺序发生变化，则需要标记从前序移动到后序的节点，相对顺序没有变更的可直接复用。
比较完成后，将剩余的 oldFiber 遍历删除。最后剩下的就是 newFiber 数组。
React 通过 Diff 算法达到复用已经有的节点从而提高性能的目的。在 React 中，节点以 Virtual DOM 的形态存在，Diff 则是将新老 DOM 树进行对比，尽可能的复用已经存在的 DOM 节点，减少插入、删除等 DOM 操作。
React 通过对比 currentFiber 和 nextFiber 的 child 字段，进行 Diff：