基于单向链表的 fiber reconciler

React.js 底层设计原则是尽可能优先响应用户交互 user interaction（不能及时响应就会造成卡顿），那么所有 react 底层代码执行必须限制在有限时间内。因为当前现代浏览器基准刷效率普遍为 60hz，即单帧是 16ms(=1s/60hz)。基于 WHATWG 所起草的规范 HTML Living Standard 关于 event loop processing model 的阐述，在单帧内必须给 ui rendering 留出一定时间，否则过长的 JS 执行会导致单帧内剩余时间不足以在当前 event loop 中处理 UI rendering 时，将跳过 ui rendering，进而导致画面卡顿，即 drop frame。

oneFrame = jsExecution + styleCalculation + layout + paint + composite

stack reconciler

在 react v15 中，reconciler 是基于 stack 基本数据结构实现的 递归型 reconciler（官方名为 stack reconciler）。其核心特点在于 n 叉树的深度优先遍历，更加准确来说是前序遍历。为了便于理解其核心实现路径，我们给定如下 internal react instance 结构：

interface Instance {
  type: string
  render: () => Instance[]
}

根据给定的类型定义一个示例 react instance tree：

const a: Instance = { type: 'a', render: () => [b, c] }
const b: Instance = { type: 'b', render: () => [d] }
const c: Instance = { type: 'c', render: () => [e] }
const d: Instance = { type: 'd', render: () => [] }
const e: Instance = { type: 'e', render: () => [] }

根据深度优先遍历的定义创建一个基于递归的前序遍历实现：

const debug = console.trace

export function dfs(instance: Instance) {
  const { type } = instance
  debug(type)
  const children = instance.render()
  children.forEach(dfs)
}

上述递归的结束条件是当当前树节点无子节点时，将终止递归，并回到上一层遍历后续的兄弟节点。代码中 console.trace 调用将有助于我们理解遍历各个节点时的调用栈情况。

传入根节点 a 将得到以下调用输出：

a
   dfs @ VM176:10
   (anonymous) @ VM202:1
b
   dfs @ VM176:10
   dfs @ VM176:12
   (anonymous) @ VM202:1
d
   dfs @ VM176:10
   dfs @ VM176:12
   dfs @ VM176:12
   (anonymous) @ VM202:1
c
   dfs @ VM176:10
   dfs @ VM176:12
   (anonymous) @ VM202:1
e
   dfs @ VM176:10
   dfs @ VM176:12
   dfs @ VM176:12
   (anonymous) @ VM202:1

再次提醒，上文代码非实际 React.js 实现，侧重点在于代码所表示的核心意义，而非实际代码本身。

深入理解示例代码可见，基于上文递归的前序遍历作用于 instance tree 时，各个子节点的遍历严格依赖于其父级节点，并且这种依赖关系 由调用栈的嵌套关系 所决定。当树的节点过多势必造成长时间的遍历。回想起来，react 中这种长时间阻塞 execution context stack 的场景如同早期 OS 的 first come, first served 调度算法一般——先到先得，首先进入队列的进程任务始终优先执行，但是，当前面的进程长时间占用 CPU 资源时，整个系统就会假死，以至于后续的进程任务都被 “饿死”（starvation）。

fist come, first served 亦称 fist come, first out (a.k.a, FIFO)

后续，OS 为了避免系统饿死，并给予其他进程均有执行的机会，那么 OS 被设计为在一定时候后就会转而执行其他进程，以此往复，所有的进程任务均通过 “抢占” 来得到执行机会。同样地，在 UI 更新领域，我们应该拆分整个遍历找到更新点的这一过程，以防止长时间的遍历过程占用 execution context stack。

但是，问题出现了，若我们基于栈结构实现拆分遍历的整个过程，我们要维护整个调用栈，而不仅仅是栈顶的栈帧。对于大量中间态的维护也可能会存在缓存更新不及时等一系列性能问题。至此，我们没有一个优雅的方式拆分遍历，并且适时根据任务优先级调整遍历的节点顺序。

从上文看出似乎因为递归的实现导致了一些致命的性能问题，那么我们改变树的遍历方式，改为 迭代法 实现树的深度优先遍历是否就可以解决上述问题？以下给出基于迭代法的深度优先遍历 —— 前序遍历的解法：

export function dfs(instance: Instance) {
  const stack: Instance[] = [instance]
  while (stack.length) {
    const current = stack.pop()!
    debug(current.type)
    const renderedElement = current.render()

    // 前序遍历始终优先遍历左子节点，故先 push 右节点
    for (let i = renderedElement.length - 1; i > -1; i--) {
      stack.push(renderedElement[i])
    }
  }
}

得到如下日志记录：

a
   dfs @ VM401:5
   (anonymous) @ VM433:1
b
   dfs @ VM401:5
   (anonymous) @ VM433:1
d
   dfs @ VM401:5
   (anonymous) @ VM433:1
c
   dfs @ VM401:5
   (anonymous) @ VM433:1
e
   dfs @ VM401:5
   (anonymous) @ VM433:1

与递归解法不同的是，迭代法不再递归调用 dfs 函数，而是通过构建一个迭代循环来遍历树的每个节点。迭代法虽然并未依赖调用栈的 stack 结构，但其在依赖迭代过程中，仍严格遵循节点顺序，并且内部构建的中间变量仍需要使用 stack 结构作为中间结构来回溯到上一层节点，以完成前序遍历。实质上，迭代法 并未改变对 stack 数据结构和对 first come first serve 策略的实际依赖的本质。

那么至此，我们知道，stack reconciler 的特点在于一旦 reconciler 开始执行，就会从 root node 开始向 child node 递归深度优先遍历直至完整的树遍历完成。显而易见，此时整个协调过程是 同步且连续执行。在整个遍历过程中，存在的一个致命隐患就是，一旦树节点过多，必然导致长时间的递归调用遍历。那么结合前文关于 event loop processing model 的阐述，长时间的同步遍历将难以给予 ui rendering 充足时间。此时的 n 叉树遍历执行将长时间占用宝贵的 execution context stack 资源，此时所有的诸如用户交互之类的 marco-task 也将长时间在 task queue 中等待而得不到响应，如同采用了 first come first serve 调度策略的 OS 进程被 “饿死”。

回顾之前的一切都是因为 stack 结构的特性并 不适合 需要拆分遍历过程且能够调整部分节点遍历顺序的场景。

基本数据结构的转变

前文我们已经得到 stack reconciler 的问题，并且给出了目标。那么我们借由反向思考，为了避免 JS execution context stack 被长时间占用，我们就不能够再直接使用基于 stack 结构的递归遍历，一是因为递归可能造成非常深的调用栈，二是递归遍历很难优雅中断，恢复，复用中间状态。我们就不得不需要将整个树的遍历过程 打散，并且额外需要基于离散化的遍历方式对高优先级的任务进行调度，使其得到优先执行。

前文已经说到所有的 react 组件实例构成 n 叉树这一基本数据结构，而树结构在图论中属于无向无环图，而树是图的特例，而树的特例是链表，即当一棵树除叶子节点外的所有节点有且仅有一个直接子节点时，将构成链表结构。在某种程度上来说，所有的树结构都能够转化为多个链表相交的组合体。那么树的遍历问题可以转化为 多条相交链表的遍历。

另外，链表本质上属于有向图，那么它的一大特点就是具有方向，单链表具有唯一的方向，双向链表具有两个方向。当我们采用多条链表遍历的方式来代替原有的树的遍历时，最大的区别就是 脱离了对栈结构的依赖。因为从链表遍历和树遍历的本质来讲，链表遍历严格按照链表方向，并且对应唯一的下一个节点，所以在遍历过程中不再需要像树的遍历那样使用栈作为中间数据结构，以保证在遍历完当前节点后要对先前节点进行 回溯（以继续遍历当前节点的兄弟节点）。至此，将树结构遍历转变为多条链表的遍历从根本上解决了树遍历的中断时，中间状态的保持问题——我们仅仅需要保持对中断时所对应的链表节点的引用即可。

let root: Fiber = rootFiber
let current: Fiber = rootFiber

while (true) {
  // 子代优先，深入子节点，直至树的叶子节点
  if (current.child) {
    current = current.child // 基本的链表遍历语句
    continue // 一直遍历到 child 属性所在链表的尾节点，即树的叶子节点
  }
  // root 无子代时，跳出遍历
  if (current === root) {
    return
  }

  while (!current.sibling) {
    if (!current.return || current.return === root) {
      return
    }
    current = current.return // 切换至 return 链表
  }

  current = current.sibling // 切换至 sibling 链表
}

以上代码非 React.js 内部代码，仅仅为了体现链表遍历树节点的思维模式。

上文借鉴了 React fiber 的字段给出了一个表现了前文的链表优势的示例代码。current 变量表示当前遍历到的树中的节点，并且由上文遍历代码可见，我们将原有的树结构转变为了 三种链表 构成的结合体：

1. 由所有子节点的 child 字段构成的单向链表；

2. 树的每层节点的 sibling 构成的单向链表，此时兄弟节点的遍历又构成了树的层序遍历（广度优先遍历）；

3. 由所有叶子节点（无子节点的树节点）通过 return 字段构成的链表；

中断、恢复遍历

继承前一章节代码，当我们在上文遍历的开头加入判断语句时，那么此时就可以实现任意的中断，并且此时仅仅需要保留对 current 节点的引用，即可在后续任意时刻恢复之前未完成的遍历。

let current: Fiber = rootFiber

function workLoop() {
  while (current !== null) {
    if (shouldYield()) {
      break
    }
    // ...
  }
}

当循环被 break 后，在后续任意时刻再次调用 workLoop 函数时，将从 current 节点恢复先前未完成的树节点遍历，而不是从根节点开始遍历。

结论

至此，在这篇文章中，我们由 stack reconciler 不可调和的性能缺陷出发，由对树结构的节点遍历行为分析出我们无法优雅解决遍历中断的状态保持问题的核心关键点在于——普通的树的节点遍历不论是递归法还是迭代法均对栈结构产生了依赖，并且栈结构本身的特点决定了它并不适用于需要中断遍历的场景。

后续我们通过对树结构的抽象发现，当一棵树除叶子节点外的其他节点均只有一个子节点时，此时的树结构不正是无方向的链表结构吗？至此我们得出任意的树结构均能转化为多个链表的组合体的结论，并据此将树的遍历行为转变为基于多个链表的遍历行为。

而链表本质上是离散性存储结构，它的遍历仅仅依赖于链表的方向，因为不像树的深度优先遍历依赖栈结构进行回溯，所以链表并不需要栈结构作为遍历的中间结构。至此我们规避了对栈结构的依赖，从而解决了遍历时的中间态问题。

参考

• Github(facebook/react#7942) - Fiber Principles: Contributing To Fiber
• Google Web fundamentals - rendering performance