出處：https://segmentfault.com/a/1190000039180494

背景介紹

Fiber架構主要有兩個階段, reconciliation(協調)和commit(提交)。協調階段通常稱為渲染階段。此時會發生：

更新state和props呼叫生命週期檢索子級比較和之前子級的區別更新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).每個獨立的棧幀包含：

函式的返回地址和引數臨時變數: 包括函式的非靜態區域性變數以及編譯器自動生成的其他臨時變數函式呼叫的上下文棧是從高地址向低地址延伸,一個函式的棧幀用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, c2walk(a1)

遞迴遍歷元件樹的方法很直接，但是它有侷限性，它無法在特定的元件上暫停工作。如果透過這種方法，React會一直保持迭代，直到處理完所有元件並且堆疊為空為止。

那麼Fiber架構是如何做到不需要遞迴而遍歷樹的呢？React使用了單鏈表樹。可以隨時暫停遍歷

連結串列樹遍歷

關於連結串列樹遍歷演算法的要點請看 這裡

如果需要實現連結串列樹的遍歷，連結串列樹的每個節點需要包含下面三個屬性：

child, 第一個子級的引用sibling, 第一個同級的引用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);

建立完成，單鏈表的結構應該如下圖所示：

// trueconsole.log(parent.child.instance.name === 'b1');// trueconsole.log(child.sibling.instance.name === 'b2');// trueconsole.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的思路

從根節點root獲取第一個子節點如果root有子節點，將當前指標設定為第一個子節點，並進入下一次迭代。（深度優先遍歷）如果root的第一個子節點，沒有子節點，則嘗試獲取它的第一個兄弟節點。如果有兄弟節點，將當前指標設定為第一個子節點，然後兄弟節點進入深度優先遍歷。如果沒有兄弟節點，則返回父節點。最後結束遍歷

節點遍歷的過程如下圖：

我們現在保留對當前堆疊幀的引用，就可以隨時停止遍歷然後再恢復遍歷

function walk(o) {    let root = o;    let current = o;    while (true) {            ...            current = child;            ...                        current = current.return;            ...            current = current.sibling;    }}

:rocket: :rocket: :rocket: 原文在這裡沒有舉例子說明，我想在這裡實現一個例子，來說明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)

作者：張越

出處：https://segmentfault.com/a/1190000039180494