前情提要
上一篇我们提到如果 setState 之后，虚拟 dom diff 比较耗时，那么导致浏览器 FPS 降低，使得用户觉得页面卡顿。那么 react 新的调度算法就是把原本一次 diff 的过程切分到各个帧去执行，使得浏览器在 diff 过程中也能响应用户事件。接下来我们具体分析下新的调度算法是怎么回事。
原虚拟 DOM 问题
假设我们有一个 react 应用如下：
class App extends React.Component {
render() {
return (
<div>
<div>{this.props.name}</div>
<ul>
<li>{this.props.items[0]}</li>
<li>{this.props.items[1]}</li>
</ul>
</div>
);
}
}
整个 app 的虚拟 dom 大致是这样的：
var rootHost = {
type: ‘div’,
children: [{
type: ‘div’,
children: [{type: ‘text’} ]
}. {
type: ‘ul’,
children: [
{type: ‘li’, children:[ {type: ‘text’} ] },
{type: ‘li’, children:[ {type: ‘text’} ] }
]
} ]
}
当更新发生 diff 两棵新老虚拟 dom 树的时候是递归的逐层比较（如下图）。这个过程是一次完成的，如果要按上一篇我们说的把 diff 过程切割成好多时间片来执行，难度是如何记住状态且恢复现场。譬如说你 diff 到一半函数返回了，等下一个时间片继续 diff。如果只记住上次递归到哪个节点，那么你只能顺着他的 children 继续 diff，而它的兄弟节点就丢失了。如果要完美恢复现场保存的结构估计得挺复杂。所以 react16 改造了虚拟 dom 的结构，引入了 fiber 的链表结构。
现在解决方案 – fiber
fiber 节点相当于以前的虚拟 dom 节点，结构如下：
const Fiber = {
tag: HOST_COMPONENT,
type: “div”,
return: parentFiber,
child: childFiber,
sibling: null,
alternate: currentFiber,
stateNode: document.createElement(“div”)| instance,
props: {children: [], className: “foo”},
partialState: null,
effectTag: PLACEMENT,
effects: []
};
先讲重要的几个属性：return 存储的是当前节点的父节点（元素），child 存储的是第一个子节点（元素），sibling 存储的是他右边第一个的兄弟节点（元素）。alternate 保存是当更新发生时候同一个节点带有新的 props 和 state 生成的新 fiber 节点。那么虚拟 dom 的存储结构用链表的形式描述了整棵树。
从顶层开始左序深度优先遍历如下图所示：
我们在遍历 dom 树 diff 的时候，即使中断了，我们只需要记住中断时候的那么一个节点，就可以在下个时间片恢复继续遍历并 diff。这就是 fiber 数据结构选用链表的一大好处。我先用文字大致描述下 fiber diff 算法的过程再来看代码。从跟节点开始遍历，碰到一个节点和 alternate 比较并记录下需要更新的东西，并把这些更新提交到当前节点的父亲。当遍历完这颗树的时候，再通过 return 回溯到根节点。这个过程中把所有的更新全部带到根节点，再一次更新到真实的 dom 中去。
从根节点开始：
div1 通过 child 到 div2。
div2 和自己的 alternate 比较完把更新 commit1 通过 return 提交到 div1。
div2 通过 sibling 到 ul1。
ul1 和自己的 alternate 比较完把更新 commit2 通过 return 提交到 div1。
ul1 通过 child 到 li1。
li1 和自己的 alternate 比较完把更新 commit3 通过 return 提交到 ul1。
li1 通过 sibling 到 li2。
li2 和自己的 alternate 比较完把更新 commit4 通过 return 提交到 ul1。
遍历完整棵树开始回溯，li2 通过 return 回到 ul1。
把 commit3 和 commit4 通过 return 提交到 div1。
ul1 通过 return 回到 div1。
获取到所有更新 commit1-4，一次更新到真是的 dom 中去。
使用 fiber 算法更新的代码实现
React.Component.prototype.setState = function(partialState, callback) {
updateQueue.pus({
stateNode: this,
partialState: partialState
} );
requestIdleCallback(performWork); // 这里就开始干活了
}
function performWork(deadline) {
workLoop(deadline)
if (nextUnitOfWork || updateQueue.length > 0) {
requestIdleCallback(performWork) // 继续干
}
}
setState 先把此次更新放到更新队列 updateQueue 里面，然后调用调度器开始做更新任务。performWork 先调用 workLoop 对 fiber 树进行遍历比较，就是我们上面提到的遍历过程。当此次时间片时间不够遍历完整个 fiber 树，或者遍历并比较完之后 workLoop 函数结束。接下来我们判断下 fiber 树是否遍历完或者更新队列 updateQueue 是否还有待更新的任务。如果有则调用 requestIdleCallback 在下个时间片继续干活。nextUnitOfWork 是个全局变量，记录 workLoop 遍历 fiber 树中断在哪个节点。
function workLoop(deadline) {
if (!nextUnitOfWork) {
// 一个周期内只创建一次
nextUnitOfWork = createWorkInProgress(updateQueue)
}
while (nextUnitOfWork && deadline.timeRemaining() > EXPIRATION_TIME) {
nextUnitOfWork = performUnitOfWork(nextUnitOfWork)
}
if (pendingCommit) {
// 当全局 pendingCommit 变量被负值
commitAllwork(pendingCommit)
}
}
刚开始遍历的时候判断全局变量 nextUnitOfWork 是否存在？如果存在表示上次任务中断了，我们继续，如果不存在我们就从更新队列里面取第一个任务，并生成对应的 fiber 根节点。接下来我们就是正式的工作了，用循环从某个节点开始遍历 fiber 树。performUnitOfWork 根据我们上面提到的遍历规则，在对当前节点处理完之后，返回下一个需要遍历的节点。循环除了要判断是否有下一个节点（是否遍历完），还要判断当前给你的时间是否用完，如果用完了则需要返回，让浏览器响应用户的交互事件，然后再在下个时间片继续。workLoop 最后一步判断全局变量 pendingCommit 是否存在，如果存在则把这次遍历 fiber 树产生的所有更新一次更新到真实的 dom 上去。注意 pendingCommit 在完成一次完整的遍历过程之前是不会有值的。
function createWorkInProgress(updateQueue) {
const updateTask = updateQueue.shift()
if (!updateTask) return
if (updateTask.partialState) {
// 证明这是一个 setState 操作
updateTask.stateNode._internalfiber.partialState = updateTask.partialState
}
const rootFiber =
updateTask.fromTag === tag.HostRoot
? updateTask.stateNode._rootContainerFiber
: getRoot(updateTask.stateNode._internalfiber)
return {
tag: tag.HostRoot,
stateNode: updateTask.stateNode,
props: updateTask.props || rootFiber.props,
alternate: rootFiber // 用于链接新旧的 VDOM
}
}
function getRoot(fiber) {
let _fiber = fiber
while (_fiber.return) {
_fiber = _fiber.return
}
return _fiber
}
createWorkInProgress 拿出更新队列 updateQueue 第一个任务，然后看触发这个任务的节点是什么类型。如果不是根节点，则通过循环迭代节点的 return 找到最上层的根节点。最后生成一个新的 fiber 节点，这个节点就是当前 fiber 节点的 alternate 指向的，也就是说下面会在当前节点和这个新生成的节点直接进行 diff。
function performUnitOfWork(workInProgress) {
const nextChild = beginWork(workInProgress)
if (nextChild) return nextChild
// 没有 nextChild, 我们看看这个节点有没有 sibling
let current = workInProgress
while (current) {
// 收集当前节点的 effect，然后向上传递
completeWork(current)
if (current.sibling) return current.sibling
// 没有 sibling，回到这个节点的父亲，看看有没有 sibling
current = current.return
}
}
performUnitOfWork 做的工作是 diff 当前节点，diff 完看看有没有子节点，如果没有子节点则把更新先提交到父节点。然后再看有没有兄弟节点，如果有则返回出去当作下次遍历的节点。如果还是没有，说明整个 fiber 树已经遍历完了，则进入到回溯过程，把所有的更新都集中到根节点进行更新真实 dom。
function completeWork(currentFiber) {
if (currentFiber.tag === tag.classComponent) {
// 用于回溯最高点的 root
currentFiber.stateNode._internalfiber = currentFiber
}
if (currentFiber.return) {
const currentEffect = currentFiber.effects || [] // 收集当前节点的 effect list
const currentEffectTag = currentFiber.effectTag ? [currentFiber] : []
const parentEffects = currentFiber.return.effects || []
currentFiber.return.effects = parentEffects.concat(currentEffect, currentEffectTag)
} else {
// 到达最顶端了
pendingCommit = currentFiber
}
}
我们看到 completeWork 中当判断到当前节点是根节点的时候才赋值 pendingCommit 整个全局变量。
function commitAllwork(topFiber) {
topFiber.effects.forEach(f => {
commitWork(f)
})
topFiber.stateNode._rootContainerFiber = topFiber
topFiber.effects = []
nextUnitOfWork = null
pendingCommit = null
}
当回溯完，有了 pendingCommit，则 commitAllwork 会被调用。它做的工作就是循环遍历根节点的 effets 数据，里面保存着所有要更新的内容。commitWork 就是执行具体更新的函数，这里就不展开了（因为这篇主要想讲的是 fiber 更新的调度算法）。
所以你们看遍历 dom 数 diff 的过程是可以被打断并且在后续的时间片上接着干，只是最后一步 commitAllwork 是同步的不能打断的。这样 react 使用新的调度算法优化了更新过程中执行时间过长导致的页面卡顿现象。
参考文献
为 Luy 实现 React Fiber 架构 – 更详细的代码实现可以看这片文章。