React Fiber 渐进式遍历详解

GraphQuery 发布于2019-08-26 13:50 / 1056人阅读

摘要：今天将手写一个，详细讲解遍历链的实现方式。可以看到循环的结束条件是当前处理的节点等于根节点。下面再来看看怎么结合，实现渐进式遍历。

欢迎关注我的公众号睿Talk，获取我最新的文章：

一、前言

之前写的一篇文章，React Fiber 原理介绍，介绍了 React Fiber 的实现原理，其中的关键是使用Fiber链的数据结构，将递归的Stack Reconciler改写为循环的Fiber Reconciler。今天将手写一个 demo，详细讲解遍历Fiber链的实现方式。

二、Stack Reconciler

假设有以下组件树：

对应的 JS 代码如下：

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 = () => [];

使用Stack Reconciler递归的方式来遍历组件树，大概是这个样子：

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

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

walk(a1);

// 输出结果：a1, b1, b2, c1, d1, d2, b3, c2

二、Fiber Reconciler

下面我们用 Fiber 的数据结构来改写遍历过程。首先定义数据结构，然后在遍历的过程中通过link方法创建节点间的关系：

// 定义 Fiber 数据结构
class Node {
    constructor(instance) {
        this.instance = instance;
        this.child = null;
        this.sibling = null;
        this.return = null;
    }
}

// 创建关系链
function link(parent, children) {
    if (children === null) children = [];

    // child 指向第一个子元素
    parent.child = children.reduceRight((previous, current) => {
        const node = new Node(current);
        node.return = parent;
        // sibling 指向前面处理的元素
        node.sibling = previous;
        return node;
    }, null);

    return parent.child;
}

遍历完成后会得出如下的关系链：

下面来详细看下遍历的过程。还是沿用之前的walk和doWork方法名：

function doWork(node) {
    console.log(node.instance.name);
    
    // 创建关系链
    const children = node.instance.render();
    return link(node, children);
}

function walk() {
    while (true) {
        let child = doWork(node);

        if (child) {
            node = child;
            continue;
        }

        if (node === root) {
            return;
        }

        while (!node.sibling) {
            if (!node.return || node.return === root) {
                return;
            }

            node = node.return;
        }

        node = node.sibling;
    }
}

const hostNode = new Node(a1);

const root = hostNode;
let node = root;

walk();

// 输出结果：a1, b1, b2, c1, d1, d2, b3, c2

上面就是递归改循环的代码了。可以看到循环的结束条件是当前处理的节点等于根节点。在循环开始的时候，以深度优先一层一层往下递进。当没有子节点和兄弟节点的时候，当前节点会往上层节点回溯，直至根节点为止。

下面再来看看怎么结合requestIdleCallback API，实现渐进式遍历。由于完成这个遍历所需时间实在太短，因此每处理 3 个节点，我们sleep 1 秒，从而达到退出当前requestIdleCallback的目的，然后再创建一个新的回调任务：

function sleep(n) {
    const start = +new Date();
    while(true) if(+new Date() - start > n) break;
}

function walk(deadline) {
    let i = 1;

    while (deadline.timeRemaining() > 0 || deadline.didTimeout) {
        console.log(deadline.timeRemaining(), deadline.didTimeout);

        let child = doWork(node);

        if (i > 2) {
            sleep(1000);
        }
        i++;

        if (child) {
            node = child;
            continue;
        }

        if (node === root) {
            console.log("================ Task End ===============");
            return;
        }

        while (!node.sibling) {
            if (!node.return || node.return === root) {
                console.log("================ Task End ===============");
                return;
            }

            node = node.return;
        }

        node = node.sibling;
    }

    console.log("================ Task End ===============");

    requestIdleCallback(walk);
}

requestIdleCallback(walk);

// 输出结果：
15.845 false
a1
15.14 false
b1
14.770000000000001 false
b2
================ Task End ===============
15.290000000000001 false
c1
14.825000000000001 false
d1
14.485000000000001 false
d2
================ Task End ===============
14.96 false
b3
14.475000000000001 false
c2
================ Task End ===============

三、总结

本文通过一个 demo，讲解了如何利用React Fiber的数据结构，递归改循环，实现组件树的渐进式遍历。

GPU服务器私有云 react-fiber Fiber 渐进式渐进填充

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/109642.html

【译】React及React Fiber基本的设计理念

摘要：基础的理论概念这篇文章是我的一次尝试，希望能够形式化的介绍关于本身的一些理念模型。我对于此实际的理念模型是在每次的更新过程中返回下一个阶段的状态。的目标是提升对在动画，布局以及手势方面的友好度。我已经邀请了团队的成员来对本文档的准确性进行。前言本文主要是对收集到的一些官方或者其他平台的文章进行翻译，中间可能穿插一些个人的理解，如有错误疏漏之处，还望批评指正。笔者并未研究过源码，只是...

lewif 2019-08-20 15:47 评论0 收藏0
React Fiber 原理介绍

摘要：如果运算持续占用主线程，页面就没法得到及时的更新。三解题思路解决主线程长时间被运算占用这一问题的基本思路，是将运算切割为多个步骤，分批完成。这颗新树每生成一个新的节点，都会将控制权交回给主线程，去检查有没有优先级更高的任务需要执行。欢迎关注我的公众号睿Talk，获取我最新的文章：showImg(https://segmentfault.com/img/bVbmYjo); 一、前言在...

leap_frog 2019-08-23 15:24 评论0 收藏0
React16性能改善的原理（二）

摘要：接下来我们就是正式的工作了，用循环从某个节点开始遍历树。最后一步判断全局变量是否存在，如果存在则把这次遍历树产生的所有更新一次更新到真实的上去。前情提要上一篇我们提到如果 setState 之后，虚拟 dom diff 比较耗时，那么导致浏览器 FPS 降低，使得用户觉得页面卡顿。那么 react 新的调度算法就是把原本一次 diff 的过程切分到各个帧去执行，使得浏览器在 dif...

guqiu 2019-08-26 13:37 评论0 收藏0
Deep In React之浅谈 React Fiber 架构(一)

摘要：在上面我们已经知道浏览器是一帧一帧执行的，在两个执行帧之间，主线程通常会有一小段空闲时间，可以在这个空闲期调用空闲期回调，执行一些任务。另外由于这些堆栈是可以自己控制的，所以可以加入并发或者错误边界等功能。文章首发于个人博客前言 2016 年都已经透露出来的概念，这都 9102 年了，我才开始写 Fiber 的文章，表示惭愧呀。不过现在好的是关于 Fiber 的资料已经很丰富了，...

Jiavan 2019-08-23 18:19 评论0 收藏0
「React 16」为 Luy 实现 React Fiber 架构

摘要：开始写代码构造函数讲了那么多的理论，大家一定是晕了，但是没办法，架构已经比之前的简单要复杂太多了，因此不可能指望一次性把的内容全部理解，需要反复多看。前言 Facebook 的研发能力真是惊人， Fiber 架构给 React 带来了新视野的同时，将调度一词介绍给了前端，然而这个架构实在不好懂，比起以前的 Vdom 树，新的 Fiber 树就麻烦太多。可以说，React 16 和 ...

DevWiki 2019-08-22 17:26 评论0 收藏0