React Fiber 渐进式组件遍历详解

欢迎关注我的公众号 睿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 的数据结构，递归改循环，实现组件树的渐进式遍历。