React Fiber 漸進(jìn)式遍歷詳解

GraphQuery 發(fā)布于2019-08-26 13:50 / 1151人閱讀

摘要：今天將手寫一個(gè)，詳細(xì)講解遍歷鏈的實(shí)現(xiàn)方式。可以看到循環(huán)的結(jié)束條件是當(dāng)前處理的節(jié)點(diǎn)等于根節(jié)點(diǎn)。下面再來看看怎么結(jié)合，實(shí)現(xiàn)漸進(jìn)式遍歷。

歡迎關(guān)注我的公眾號(hào)睿Talk，獲取我最新的文章：

一、前言

之前寫的一篇文章，React Fiber 原理介紹，介紹了 React Fiber 的實(shí)現(xiàn)原理，其中的關(guān)鍵是使用Fiber鏈的數(shù)據(jù)結(jié)構(gòu)，將遞歸的Stack Reconciler改寫為循環(huán)的Fiber Reconciler。今天將手寫一個(gè) demo，詳細(xì)講解遍歷Fiber鏈的實(shí)現(xiàn)方式。

二、Stack Reconciler

假設(shè)有以下組件樹：

對(duì)應(yīng)的 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遞歸的方式來遍歷組件樹，大概是這個(gè)樣子：

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

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

walk(a1);

// 輸出結(jié)果：a1, b1, b2, c1, d1, d2, b3, c2

二、Fiber Reconciler

下面我們用 Fiber 的數(shù)據(jù)結(jié)構(gòu)來改寫遍歷過程。首先定義數(shù)據(jù)結(jié)構(gòu)，然后在遍歷的過程中通過link方法創(chuàng)建節(jié)點(diǎn)間的關(guān)系：

// 定義 Fiber 數(shù)據(jù)結(jié)構(gòu)
class Node {
    constructor(instance) {
        this.instance = instance;
        this.child = null;
        this.sibling = null;
        this.return = null;
    }
}

// 創(chuàng)建關(guān)系鏈
function link(parent, children) {
    if (children === null) children = [];

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

    return parent.child;
}

遍歷完成后會(huì)得出如下的關(guān)系鏈：

下面來詳細(xì)看下遍歷的過程。還是沿用之前的walk和doWork方法名：

function doWork(node) {
    console.log(node.instance.name);
    
    // 創(chuàng)建關(guān)系鏈
    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();

// 輸出結(jié)果：a1, b1, b2, c1, d1, d2, b3, c2

上面就是遞歸改循環(huán)的代碼了。可以看到循環(huán)的結(jié)束條件是當(dāng)前處理的節(jié)點(diǎn)等于根節(jié)點(diǎn)。在循環(huán)開始的時(shí)候，以深度優(yōu)先一層一層往下遞進(jìn)。當(dāng)沒有子節(jié)點(diǎn)和兄弟節(jié)點(diǎn)的時(shí)候，當(dāng)前節(jié)點(diǎn)會(huì)往上層節(jié)點(diǎn)回溯，直至根節(jié)點(diǎn)為止。

下面再來看看怎么結(jié)合requestIdleCallback API，實(shí)現(xiàn)漸進(jìn)式遍歷。由于完成這個(gè)遍歷所需時(shí)間實(shí)在太短，因此每處理 3 個(gè)節(jié)點(diǎn)，我們sleep 1 秒，從而達(dá)到退出當(dāng)前requestIdleCallback的目的，然后再創(chuàng)建一個(gè)新的回調(diào)任務(wù)：

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

// 輸出結(jié)果：
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 ===============

三、總結(jié)

本文通過一個(gè) demo，講解了如何利用React Fiber的數(shù)據(jù)結(jié)構(gòu)，遞歸改循環(huán)，實(shí)現(xiàn)組件樹的漸進(jìn)式遍歷。