Fiber内部:深度概览React中新的调和算法

Inside Fiber: in-depth overview of the new reconciliation algorithm in React

Posted by wuqiuyu on September 3, 2019

Maxim Koretskyi 大神关于 react 的系列文章之一,原文地址:The how and why on React’s usage of linked list in Fiber to walk the component’s tree
React 的 reconciler 的遍历算法

  为了培训我自己和社区,我花了很多的时间在web 逆向工程技术并且记录我的发现。去年,我把绝大部分精力都用来研究 Angular 的源码,产出了网络中最大的 Angular 出版物——Angular-In-Depth。现在是时候深入研究 React 了。变化检测 是我在 Angular 中专长的主要的技术领域。通过付出一些耐心和更多的调试,我希望我能够在快速的 React 达到这样的水平。
  在 React 中,变化检测的机制通常被认为是“调和”或者“渲染”,Fiber 是最新的实现。由于基础结构提供了很多能力去实现一些有意思的特性,例如执行无阻塞的渲染、根据优先级执行更新和在后台预渲染内容。这些特性在并发的 React 哲学中被称为时间切片。
  除了处理解决应用开发人员的问题,这些内部的实现机制很多是来自于广泛的工程学观念上的诉求。源码中大量的知识财富可以帮助我们作为工程师更好的成长。
  现在如果你用 Google 搜索“React Fiber”你可以在结果中看到很多的文章。所有的这些文章,除了Andrew Clark 的这篇都是非常高深的解释。在这篇文章中,我会参考 Andrew Clark 的这篇,对 Fiber 中一些非常重要的概念提供一个更详尽的解释。一旦我们完成这些,你会对Lin Clark 在 ReactConf 2017的关于事件循环的概念有一个深入的理解。这个演讲你需要看看,但是花一些时间阅读文本之后,对你来说会更容易理解。
  这篇文章是 React 的 Fiber 内部机制一个系列的开端。我大约 70%的是通过理解内部实现了解的,此外还看了三篇关于协调和渲染机制的文章。
  让我们开始吧!

打基础

  Fiber 架构具有 2 个主要的阶段: reconciliation/render 和 commit。在源代码中 reconciliation 阶段通常被叫做 render 阶段。这个阶段是 React 遍历组件树的阶段:
    更新 state 和 props
    调用生命周期函数
    生成组件的子组件
    新生成的子组件和之前的子组件进行比较
    计算出需要更新的 DOM 操作

  所有这些活动都被称为 Fiber 内部的工作。需要完成工作的类型根据 React 元素的类型确定。例如,对于一个类组件(Class Component),React 需要初始化一个类,但是函数组件(Functional Component)就不需要了。如何感兴趣,这里可以看到 Fiber 中所有的工作类型。这些活动就是 Andrew 讲过的:

当处理 UI 的时候,如果一次执行太多的任务,就会导致动画掉帧。

  那么什么是一次执行太多任务呢?如果 React 要同步的遍历整颗组件树,并且执行每个组件的任务。这有可能会运行超过 16ms,供应用程序代码执行其逻辑。这可能导致掉帧,从而导致视觉上的卡顿。
  那么这个问题可以解决吗?

新浏览器(包括 React Native)实现的 API 可以解决这个问题
他提到的 API 是指requestIdleCallback全局函数,用来在浏览器空闲时间调用函数队列。下面是你可以这样使用它:

requestIdleCallback(deadline => {
  console.log(deadline.timeRemaining(), deadline.didTimeout);
});

  如果你现在打开控制台,执行上面的代码,Chrome 会打印49.9 false。这个告诉我,我有 49.9 毫秒的时间去执行我要做的任务,并且我没有使用完分配给我的时间,否则deadline.didTimeout会是true。记住timeRemaining会随着浏览器做任务而马上变化,所有要随时检查。

requestIdleCallback 局限性有点大,它不能经常执行去实现平滑的 UI 渲染,所有 React 团队不得不自己实现了 requestIdleCallback

  如果我们把所有的 React 在一个组件上执行的任务放在一个performWork的函数中。然后使用requestIdleCallback去调度任务,我们的代码会像下面这样:

requestIdleCallback(deadline => {
  // while we have time, perform work for a part of the components tree
  while ((deadline.timeRemaining() > 0 || deadline.didTimeout) && nextComponent) {
    nextComponent = performWork(nextComponent);
  }
});

  我们在一个组件中执行任务,然后返回要处理的下一个组件的引用。如果不是因为一件事,这样做是可行的。你不能同步的遍历整个组件树,因为之前提到的调和算法。这正式 Andrew 提到的:

为了去执行这些 Api,你需要一种方式把渲染任务分解成增量的单元
>   为了解决这个问题,React 不得不将依赖于构建时堆栈的同步递归模型,改为使用链表和指针的异步模型。这也就是 Andrew 所说的:
如果你只依赖构建时的调用栈,那么它会保持一直工作直到调用栈空了之后。如果我们可以打断调用栈,并且手动操作栈,是不是很棒?这就是 React 的 Fiber 做的事情。 Fiber 重新实现了栈,专门用户 React 的组件。你可以把一个独立的 fiber 看作时一个虚拟的栈

关于栈

  我想你们都对调用栈的概念很熟悉了。这就是你在代码中打断点的时候,在浏览器调试工具里面看到的东西。下面是一些来自Wikipedia的相关的引用和图表

在计算机科学中,调用栈是一个堆栈,存储着计算机程序的活跃的子程序信息。调用栈存在的原因是需要追踪每一个活跃的子进程,当它们执行完后需要归还控制。一个调用栈由一系列调用帧组成。每一个调用帧对应一个还没有终止返回的子程序调用。例如,如果一个叫做 DrawLine 子程序,正在运行,被一个叫做 DrawSquare 的子程序调用,调用栈的顶部会被安排在临近的区域。
图片

为什么调用栈和 React 相关

就像我们在文章第一部分定义的一样,React 遍历组件树在调和/渲染阶段,并且执行一些组件工作。之前的调和使用同步的递归模型依赖构建时堆栈遍历树。官方关于调和的文档描述了这个过程:

默认情况下,当遍历一个 Dom 节点的子节点的时候,React 会一次性迭代所有的子节点,并且有不同的时候都会产生一个变化

  想象一下,每一个递归都加入到栈中,并且同步执行。假设我们有一个如下的组件树:
图片。   把 render 函数当作一个对象。可以把它们当作组件的实例:

const a1 = { name: 'a1' };
const b1 = { name: 'b1' };
const b2 = { name: 'b2' };
const b3 = { name: 'b3' };
const c1 = { name: 'c1' };
const c2 = { name: 'c2' };
const d1 = { name: 'd1' };
const d2 = { name: 'd2' };

a1.render = () => [b1, b2, b3];
b1.render = () => [];
b2.render = () => [c1];
b3.render = () => [c2];
c1.render = () => [d1, d2];
c2.render = () => [];
d1.render = () => [];
d2.render = () => [];

  React 需要去遍历树,并且执行每个组件的工作。简化一下,组件的工作是打印当前组件的名字并且取得它的子组件。下面是递归下是如何运行的。

递归遍历

  主要用于递归树的方法叫做walk,下面是它的实现:

walk(a1);

function walk(instance) {
  doWork(instance);
  const children = instance.render();
  children.forEach(walk);
}

function doWork(o) {
  console.log(o.name);
}

  下面是打印输出:

a1, b1, b2, c1, d1, d2, b3, c2;

  如果你对递归不熟悉,可以查看我的深入理解递归的文章
  一个递归方法是直观并且非常合适遍历树的。但是我们发展它有限制。最大的问题是我们无法把任务拆分成增量的单元。我们无法在一个特定的组件暂停并且稍后重新开始。使用这种方法,React 必须一直迭代直到执行完所有的组件并且堆栈为空。    那么 React 是如何不使用递归实现遍历算法树的算法的呢?它使用单链表遍历算法。这使得暂停遍历和阻止堆栈增长成为可能。

链表遍历

  我很幸运的找到了算法的要旨,通过Sebastian Markbåge 的这篇文章。为了实现算法,我们需要一种拥有三种数据结构的字段:

  1. child——指向第一个子节点
  2. sibling——指向第一个兄弟节点
  3. return——指向父节点

  在React新的调和算法中拥有这些字段的数据结构叫做Fiber。在内部,这个代表了React Element保存的一系列的任务。下面这种图表展示了通过链表链接的对象以及它们之间的关系

图片   所有让我们先定义自定义节点构造函数:

class Node {
  constructor(instance) {
    this.instance = instance;
    this.child = null;
    this.sibling = null;
    this.return = null;
  }
}

  以及一个将一系列节点链接到一起的函数。我们将使用它去链接通过 render 方法返回到子节点。

function link(parent, elements) {
  if (elements === null) elements = [];

  parent.child = elements.reduceRight((previous, current) => {
    const node = new Node(current);
    node.return = parent;
    node.sibling = previous;
    return node;
  }, null);

  return parent.child;
}

  函数从最近一个子节点开始遍历节点数组并且把它们连接为一条单链表。它将引用返回给链表中的第一个兄弟节点。下面是一个简单的 Demo,描述了它是怎么工作的:

const children = [{ name: 'b1' }, { name: 'b2' }];
const parent = new Node({ name: 'a1' });
const child = link(parent, children);

// the following two statements are true
console.log(child.instance.name === 'b1');
console.log(child.sibling.instance === children[1]);

  我们同样实现了一个辅助方法来帮助执行节点的任务。在我们的例子中,是打印组件的名字。但是此外也检索了子组件并且将它们连接在一起:

function doWork(node) {
  console.log(node.instance.name);
  const children = node.instance.render();
  return link(node, children);
}

  好了,现在我们开始实现遍历算法。这是一个父节点优先,深度优先算法。下面是代码:

function walk(o) {
  let root = o;
  let current = o;

  while (true) {
    // perform work for a node, retrieve & link the children
    // 执行节点任务,并且返回和连接子节点
    let child = doWork(current);

    // if there's a child, set it as the current active node
    // 如果有子节点,那么把当前节点设置为子节点
    if (child) {
      current = child;
      continue;
    }

    // if we've returned to the top, exit the function
    // 如果当前节点是根节点,那么已经到达顶部,退出函数
    if (current === root) {
      return;
    }

    // keep going up until we find the sibling
    // 一直遍历直到找到兄弟节点
    while (!current.sibling) {
      // if we've returned to the top, exit the function
      // 如果return的节点是根节点,那边退出
      if (!current.return || current.return === root) {
        return;
      }

      // set the parent as the current active node
      // 把父节点设置为当前节点
      current = current.return;
    }

    // if found, set the sibling as the current active node
    // 如果找到了兄弟节点,就把兄弟节点设置为当前节点
    current = current.sibling;
  }
}

  尽管这个实现不是特别难理解,但是你最好去试试这个,以便刚好的理解它。其中的原理是我们保持对当前节点的引用,并且在下行遍历树,直到到达叶子节点。然后我们通过 return 指针回到共同父节点。
  此时如果我们查看调用栈,将看到下面的内容: 图片   正如你所见,调用栈并没有随着遍历而增加。但是如果把debugger放在doWork函数中,并且打印节点的 name,我们会看到下面的: 图片   这就像浏览器里面的调用栈。所以利用这个算法,我们有效的使用自己的方法实现了浏览器的调用栈。这也就是 Andrew 所说的:

Fiber 是针对 React 组件重新实现了堆栈,你可以把 Fiber 当作一个虚拟的堆栈帧。

  自从我们通过保持对节点的引用从而控制了堆栈,就像一个顶部帧一样。

function walk(o) {
    let root = o;
    let current = o;

    while (true) {
            ...

            current = child;
            ...

            current = current.return;
            ...

            current = current.sibling;
    }
}

  我们可以在遍历的过程中的任何时间停止,并且在稍后重新开始遍历。这是我们能够去使用新的requestIdleCallbackAPI 的必要条件。

React 当中的工作循环

这里是React 中实现任务循环的代码

function workLoop(isYieldy) {
  if (!isYieldy) {
    // Flush work without yielding
    while (nextUnitOfWork !== null) {
      nextUnitOfWork = performUnitOfWork(nextUnitOfWork);
    }
  } else {
    // Flush asynchronous work until the deadline runs out of time.
    while (nextUnitOfWork !== null && !shouldYield()) {
      nextUnitOfWork = performUnitOfWork(nextUnitOfWork);
    }
  }
}

  正如你所见,这很好地映射到前面我提的算法。它在nextUnitOfWork变量中保存了当前 fiber 节点的引用,作为顶部帧。算法可以同步的遍历组件树,并且执行各个 fiber 节点中的任务(nextUnitOfWork)。这就是通常所说的由于 UI 事件(click, input 等等)导致的交互式更新。或者它可以异步的遍历组件树,检查是否有多余的事件用于执行 Fiber 节点的任务。函数shouldYield返回的结果基于deadlineDidExpiredeadline变量,它们在 React 执行任务的过程中经常更新。
  peformUnitOfWork函数的代码具体实现在这里