React Fiber为什么使用链表来设计组件树

背景介绍

Fiber架构主要有两个阶段, reconciliation(协调)和commit(提交)。协调阶段通常称为渲染阶段。此时会发生：

1. 更新state和props
2. 调用生命周期
3. 检索子级
4. 比较和之前子级的区别
5. 更新DOM

这些被称为Fiber的内部活动。

如果React同步遍历整个组件树，一次的更新操作过多，执行的时间可能会超过16ms以上, 会导致视觉上的卡顿。

requestIdleCallback

requestIdleCallback会在浏览器空闲的时候，执行callback。有关requestIdleCallback的内容可以查看我之前写的文章详解 requestIdleCallback

但是由于requestIdleCallback的执行频率不足以流畅的呈现UI, React团队不得不实现自己的版本

我们假定React执行更新的操作都在performWork中，并且使用requestIdleCallback，代码可能会如下所示

requestIdleCallback((deadline) => {
    while ((deadline.timeRemaining() > 0 || deadline.didTimeout) && nextComponent) {
        nextComponent = performWork(nextComponent);
    }
});

我们在一个组件上执行工作，然后返回下一个要处理的组件。我们不能像之前一样同步处理整个组件树。要解决此问题React必须从依赖堆栈的同步递归模型迁移到具有链表和指针的异步模型。

StackFrame 栈帧

每一次函数的调用,都会在调用栈(call stack)上维护一个独立的栈帧(stack frame).每个独立的栈帧一般包括:

什么是栈

在数据结构中, 栈是限定仅在表尾进行插入或删除操作的线性表。栈是一种数据结构，它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据。

什么是栈帧

每一次函数的调用,都会在调用栈(call stack)上维护一个独立的栈帧(stack frame).每个独立的栈帧包含：

1. 函数的返回地址和参数
2. 临时变量: 包括函数的非静态局部变量以及编译器自动生成的其他临时变量
3. 函数调用的上下文
4. 栈是从高地址向低地址延伸,一个函数的栈帧用ebp和esp这两个寄存器来划定范围。ebp指向当前的栈帧的底部, esp始终指向栈帧的顶部;ebp寄存器又被称为帧指针(Frame Pointer);esp寄存器又被称为栈指针(Stack Pointer);

堆栈与React

React的协调阶段，之前使用了依赖于内置递归模型, 关于协调官方文档描述了此过程

假设我们有如下的组件树：

我们最简洁的虚拟DOM，表示这个组件树

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

递归遍历组件树

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
walk(a1)

递归遍历组件树的方法很直接，但是它有局限性，它无法在特定的组件上暂停工作。如果通过这种方法，React会一直保持迭代，直到处理完所有组件并且堆栈为空为止。

链表树遍历

关于链表树遍历算法的要点请看这里

如果需要实现链表树的遍历，链表树的每个节点需要包含下面三个属性：

1. child, 第一个子级的引用
2. sibling, 第一个同级的引用
3. return， 父级的引用

在React新的协调算法中，拥有这些字段的的节点被成为Fiber。下图是一个单链表树。

首先定义下节点的构造函数

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

我们需要一个函数，链接父节点和子节点。link函数函数parent的第一个子节点。如果没有子节点返回null .

function link(parent, elements) {
    // 如果没有子节点返回空数组
    if (elements === null) elements = [];

    parent.child = elements.reduceRight((previous, current) => {
        // 创建子节点
        const node = new Node(current);
        // 设置父节点的引用
        node.return = parent;
        // 设置同级的引用，第一次迭代previous是null
        node.sibling = previous;
        return node;
    }, null);

    return parent.child;
}

创建单链表树

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

创建完成，单链表的结构应该如下图所示：

// true
console.log(parent.child.instance.name === 'b1');
// true
console.log(child.sibling.instance.name === 'b2');
// true
console.log(child.sibling.sibling === null);

遍历链表树

首先创建一个工具函数，可以打印遍历的过程，还可以链接父节点和子节点

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

接下来我们开始实现单链表树遍历算法，算法是深度优先的实现。我们首先创建一些节点

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

function walk(o) {
    // 根节点
    let root = o;
    // 指针，当前遍历到的节点
    let current = o;

    while (true) {
        // 使用doWork，连接根节点和子节点，并返回根节点的第一个子节点
        let child = doWork(current);

        // 1. 如果有子节点，将当前的指针指向子节点，并进入下一个循环（因为是优先深度）
        // 2. 如果没有子节点，略过
        if (child) {
            current = child;
            continue;
        }

        // 如果当前指针等于根节点，结束遍历
        if (current === root) {
            return;
        }

        // 如果没有兄弟，进入while循环
        while (!current.sibling) {

            // 如果当前指针等于根节点，结束遍历
            if (!current.return || current.return === root) {
                return;
            }

            // 如果没有子节点，并且没有兄弟节点，返回父级的节点
            current = current.return;
        }

        // 如果有兄弟节点，将当前指针设置为兄弟节点，进入下一次迭代
        current = current.sibling;
    }
}

walk(new Node(a1))

总结下walk的思路

1. 从根节点root获取第一个子节点
2. 如果root有子节点，将当前指针设置为第一个子节点，并进入下一次迭代。（深度优先遍历）
3. 如果root的第一个子节点，没有子节点，则尝试获取它的第一个兄弟节点。
4. 如果有兄弟节点，将当前指针设置为第一个子节点，然后兄弟节点进入深度优先遍历。
5. 如果没有兄弟节点，则返回父节点。最后结束遍历

节点遍历的过程如下图：

我们现在保留对当前堆栈帧的引用，就可以随时停止遍历然后再恢复遍历

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

    while (true) {
            ...

            current = child;
            ...
            
            current = current.return;
            ...

            current = current.sibling;
    }
}

? ? ? 原文在这里没有举例子说明，我想在这里实现一个例子，来说明fiber如何中断遍历，然后恢复遍历的, 使用了浏览器的requestIdleCallback API

// 使用sleep模拟渲染的耗费时间
function sleep (ms = 100) {
    let sleepSwitch = true
    let s = Date.now()
    while (sleepSwitch) {
        if (Date.now() - s > ms) {
            sleepSwitch = false
        }
    } 
}

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

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;
}

// 节点
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 = () => {
    sleep(60)
    return [b1, b2, b3]
};
b1.render = () => {
    return []
};
b2.render = () => {
    sleep(20)
    return [c1]
};
b3.render = () => {
    sleep(20)
    return [c2]
};
c1.render = () => {
    sleep(40)
    return [d1, d2]
};
c2.render = () => [];
d1.render = () => [];
d2.render = () => [];

const root = new Node(a1);
// 一直保持对当前节点的引用
let current = root;
// 是否渲染完成
let isRendered = false;

const rIcb = (deadline) => {
    if (deadline.timeRemaining() > 20) {
        walk(current, deadline)
    } else {
        requestIdleCallback(rIcb);
    }
}

function doWork(node, deadline) {
    if (deadline.timeRemaining() > 20) {
        console.log(node.instance.name);
        const children = node.instance.render();
        return link(node, children);
    } else {
        requestIdleCallback(rIcb);
    }
}

function walk(o, deadline) {
    while (true) {
        let child = doWork(current, deadline);
        if (child) {
            current = child;
            continue;
        }
        if (current === root) {
            return;
        }
        while (!current.sibling) {
            if (!current.return || current.return === root) {
                return;
            }
            current = current.return;
        }
        current = current.sibling;
    }
}

requestIdleCallback(rIcb);

运行结果：

从上面的例子可以看出，我们只需要拿到当前堆帧的引用，就可以暂停遍历，随后恢复遍历

React和工作循环

这是React中工作循环的代码，nextUnitOfWork变量作为顶部栈帧，保留对当前Fiber节点的引用。

function workLoop(isYieldy) {
    if (!isYieldy) {
        while (nextUnitOfWork !== null) {
            nextUnitOfWork = performUnitOfWork(nextUnitOfWork);
        }
    } else {
        while (nextUnitOfWork !== null && !shouldYield()) {
            nextUnitOfWork = performUnitOfWork(nextUnitOfWork);
        }
    }
}

React中的算法，既可以同步遍历组件树，也可以异步遍历组件树，检查在执行Fiber内部活动后后是否还剩下时间。是否需要等到一次空闲时间执行任务。函数shouldYield返回基于deadlineDidExpire和deadline变量的结果，这些变量在React为Fiber节点执行工作时不停的更新。

参考

• The how and why on React’s usage of linked list in Fiber to walk the component’s tree
• 栈帧(Stack Frame)