The How and Why on React’s usage of linked list in Fiber to walk The component’s tree

The core logic of the Work loop method for Reconciler in React

In React, change detection is usually referred to as reconciliation or rendering, and Fiber is a new implementation of this mechanism. Under this architecture, interesting features such as improved non-blocking rendering, priority-based updates, and pre-rendering content in the background can be implemented. These features are considered time-slicing in the concurrent React philosophy. In addition to solving some real problems for developers, the internal implementation of these mechanisms also has broad appeal from an engineering perspective. Valuable bits of knowledge about why will help us grow as developers.

If you Google “ReactFiber” right now, you’ll find a ton of articles about it, all of which are fairly high-level except for notes by Andrew Clark. In this article I will use this resource and provide a detailed explanation of some particularly important concepts in Fiber. By the time we’re done, you’ll have enough knowledge to understand Lin Clark’s ReactConf 2017 talk on work loops, which you’ll need to see, but I’ll let you know more after you’ve read it in general. In a series of articles on the inside of React Fiber, I spent about 70% of my time understanding the detailed implementation inside, and wrote three articles on coordination and rendering mechanisms in the process.

Let’s get started.

Set a context

Fiber architecture has two main phases: Reconciliation/Render and Commit. The coordination phase is basically referred to as the render phase in the source code. In this phase, React iterates through the component tree and:

  • Update the state and props
  • Execute the lifecycle hook function
  • Get child components
  • Compare old and new child components
  • Sort out the DOM updates that need to be performed

All of these operations are considered a work in Fiber. The type of work that needs to be operated on depends on the React Element type, for example, a Class needs to be instantiated for a Class ComponentReact, but not for a Function Component. If you’re interested, you can see the types of all work objects in Fiber here. These operations are exactly what Andrew mentioned in his talk:

One of the problems with some UIs is that if you do too many things at once, the animation will drop frames

So what does “one-time” mean? In general, React synchronously traverses the entire tree of components and performs each component’s work, and its logic may take longer than 16ms to execute. This causes frames to drop, which in turn causes the view to stall.

So. is there any way we can fix this?

Modern browsers (including React Native) implement several apis to help with this problem

A new global method API called requestIdleCallback can add methods that will be executed when the browser is idle. How can you use it yourself? If I execute this code in Chrome’s Console panel, it prints 49.9 and false. This means THAT I have 49.9ms to do what I want, and I didn’t use up the allotted time, otherwise deadline.didTimeout would be true. Remember, as long as the browser has some work to do, the timeRemaing changes and needs to be constantly checked.

RequestIdleCallback did have a bit of a usage limitation and wasn’t always implemented sufficiently to ensure smooth UI rendering, so the React team had to implement a version of it themselves.

requestIdleCallback((deadline) = > {
    // while we have time, perform work for a part of the components tree
    while ((deadline.timeRemaining() > 0|| deadline.didTimeout) && nextComponent) { nextComponent = performWork(nextComponent); }});Copy the code

We perform work on one component and return a reference to the next component to continue. This works if you don’t just deal with one thing. You can’t synchronize the entire tree of components, like the React implementation of the coordination algorithm. This is the question that Andrew raised in his talk:

In order to use these APIs (requestIdleCallback), you need a way to break down the rendering work into incrementable units

So to fix this, React had to re-implement the way it traversed the component tree: from relying on built-in call stacks to synchronizing recursive patterns to using linked lists and Pointers asynchronously. This is what Andrew wrote:

If you just rely on the built-in call stack, it will execute until the stack is empty. It would be nice if we could interrupt the call stack as needed and maintain the stack frames manually. This is the purpose of React Fiber. Fiber is a stack implemented specifically for the React component. You can also think of a Fiber as a virtual stack frame.

That’s what I’m going to talk about now.

An explanation of the stack

Assuming you’re familiar with the feel of the call stack, you can see it when you hit the browser debugger breakpoint. Here’s a reference and sample image from Wikipedia:

In computer science, a call stack is the data structure of the stack that holds information about active subroutines in a computer program. The main reason for designing the call stack is to keep track of references to each active subroutine so that control can be returned at the end of subroutine execution. A call stack consists of stack frames, each of which corresponds to an uncompleted subroutine that holds a return. For example, if a subroutine called DrawLine is executing without the DrawSquare call, the top part of the call stack would look like the following figure.

Why is the stack related to React?

As described in the first part of this article, React traverses the tree of components in the coordination/rendering phase and performs operations on the components. Previous coordination algorithms relied on the synchronous mode of the built-in call stack to traverse the tree. The official documentation for this coordination algorithm describes this process and talks a lot about recursion:

By default, when recursing the children of a DOM node, React iterates through the list of all children at the same time and computes a mutation from any diff generated at any time.

Consider that each recursive call adds a frame to the stack, and the process is synchronous. Suppose we have the following component tree:

Use the Render method to represent objects that you can think of as component instances.

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 = (a)= > [b1, b2, b3];
b1.render = (a)= > [];
b2.render = (a)= > [c1];
b3.render = (a)= > [c2];
c1.render = (a)= > [d1, d2];
c2.render = (a)= > [];
d1.render = (a)= > [];
d2.render = (a)= > [];
Copy the code

React needs to traverse the tree to perform some operations on components. For simplicity, this operation simply prints out the name of the current component and fetches the child components. Let me do it recursively.

The recursive traversal

The main method of traversing the tree is called walk and is implemented as follows:

walk(a1);

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

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

The output we get is a1, B1, B2, C1, D1, d2, B3, C2

If you’re not sure about recursion, take a look at my in-depth article on recursion.

Recursion is an intuitive and appropriate way to traverse a tree. However, there are some limitations, the biggest of which is that you can’t break the traversal process into incrementable units. You can’t stop on a particular component and then continue. So React keeps iterating until all components are processed and the recursive stack is empty.

So how does React traverse the component tree without using recursion? It uses a single-linked list traversal tree algorithm, which pauses traversal and prevents stack growth.

List cycle

Here I find Sebastian Markbage’s summary of the algorithm. To implement this algorithm, we need a data structure containing three fields:

  • Child – represents the first child node
  • Sibling – Represents the first sibling node
  • Return – Represents the parent node

In React’s new coordination algorithm environment, this data structure is called Fiber. Internally, it represents a React node that keeps queues working. See my next article for more details on this.

The following example diagram illustrates the structure of linked objects in a linked list and how they are related:

Let’s define our custom node constructor:

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

And a method that takes an array of nodes and lists them, which we use to add the children returned by the Render method to the list:

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;
}
Copy the code

This method iterates through a set of nodes starting with the last element and then links them into a singly linked list. It returns the first sibling of the list, and here’s a simple example of how it works:

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

// the following two statements are true
console.log(child.instance.name === 'b1');
console.log(child.sibling.instance === children[1]);
Copy the code

We also implemented a helper method to perform some of the node’s work. In our case, we will print the name of the component, and after the first time, we will collect the child nodes of the component and link them together.

Ok, now we are ready to implement the main loop algorithm, which is parent node first, depth-first implementation. Here’s the code for it with additional comments:

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

    while (true) {
        // perform work for a node, retrieve & link the children
        let child = doWork(current);

        // if there's a child, set it as the current active node
        if (child) {
            current = child;
            continue;
        }

        // if we've returned to the top, exit the function
        if (current === root) {
            return;
        }

        // keep going up until we find the sibling
        while(! current.sibling) {// if we've returned to the top, exit the function
            if(! current.return || current.return === root) {return;
            }

            // set the parent as the current active node
            current = current.return;
        }

        // if found, set the sibling as the current active nodecurrent = current.sibling; }}Copy the code

While the implementation is not particularly difficult to understand, you may need to perform a little to understand it. The idea is that we keep the reference to the current node, assign it repeatedly as we move down the tree until we reach the end of the branch, and then use the return pointer to return to the common parent node.

If we now examine the call stack for this implementation, we can see:

As you can see, the stack does not grow as we traverse the tree, but if you add dubugger to the doWork method and print the node name, we see something like this:

** This looks like a browser call stack. ** So with this algorithm, we effectively replace the call stack implementation of browsing with our own implementation. This is as Andrew describes it:

Fiber is a reimplementation of the stack, especially for the React component. You can think of a Fiber as a virtual stack frame.

So far, we now control the stack by keeping a reference to the node as the top frame:

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

    while (true) {... current = child; . current = current.return; . current = current.sibling; }}Copy the code

We can stop iterating at any time and continue it later. This is exactly what we want to achieve with the new requestIdleCallbackAPI.

Work loops in React

The code here implements the React work loop:

function workLoop(isYieldy) {
    if(! isYieldy) {// Flush work without yielding
        while(nextUnitOfWork ! = =null) { nextUnitOfWork = performUnitOfWork(nextUnitOfWork); }}else {
        // Flush asynchronous work until the deadline runs out of time.
        while(nextUnitOfWork ! = =null&&! shouldYield()) { nextUnitOfWork = performUnitOfWork(nextUnitOfWork); }}}Copy the code

As you can see, it corresponds nicely to the algorithm we talked about above. It keeps a reference to the current Fiber node in the nextUnitOfWork variable that is the top frame.

This algorithm synchronously traverses the tree of components and performs next step of work on each fiber node in the tree. This is usually a so-called interactive update (click, input, etc.) caused by a UI event. Or it can detect if there is time left to asynchronously traverse the component tree after a Fiber node has performed its work. The method shouldYield returns the result based on the deadlineDidExpire and Deadline variables, which are constantly updated as the React fiber node works.

**peformUnitOfWork** method depth parsing here.