关于javascript: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 必须从依赖堆栈的同步递归模型迁徙到具备链表和指针的异步模型。

如果仅依附调用堆栈，每次更新都会工作到堆栈被清空为止。如果能够随时中断调用堆栈，手动操作栈帧，会更好。这就是 Fiber 的目标，Fiber 是堆栈的从新实现，专门用于 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 的协调阶段，之前应用了依赖于内置递归模型, 对于协调官网文档形容了此过程

React 递归 DOM 节点的子元素时，React 会同时遍历两个子元素的列表；当产生差别时，生成一个 mutation。

假如咱们有如下的组件树：

咱们最简洁的虚构 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 会始终放弃迭代，直到解决完所有组件并且堆栈为空为止。

那么 Fiber 架构是如何做到不须要递归而遍历树的呢？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)