4.React Fiber architecture: linked list, Fiber node and Fiber tree

React Fiber is the core architecture of React, which organizes and manages component trees based on a linked list structure. This article will start from the basics of linked lists and gradually explore in depth Fiber nodes, Fiber trees and double buffering mechanisms, as well as the relationship between them.

1. Basics of linked lists

Before going deep into the Fiber architecture, we need to first understand the basic data structure of linked lists. A linked list is a linear collection of nodes, each node contains data and a pointer to the next node.

1.1 Basic operations and complexity analysis of linked lists

The following is the basic operation implementation of the linked list and its time complexity analysis:

class Node {
  constructor(data) {
    this.data = data
    this.next = null
  }
}

class LinkedList {
  constructor() {
    this.head = null
  }

  //Add node to end of linked list - O(n)
  append(data) {
    const newNode = new Node(data)
    if (!this.head) {
      this.head = newNode
      return
    }
    let current = this.head
    while (current.next) {
      current = current.next
    }
    current.next = newNode
  }

  //Insert node at the beginning of the linked list - O(1)
  prepend(data) {
    const newNode = new Node(data)
    newNode.next = this.head
    this.head = newNode
  }

  //Delete the node with specified data - O(n)
  delete(data) {
    if (!this.head) return
    if (this.head.data === data) {
      this.head = this.head.next
      return
    }
    let current = this.head
    while (current.next) {
      if (current.next.data === data) {
        current.next = current.next.next
        return
      }
      current = current.next
    }
  }

  // Traverse the linked list - O(n)
  traverse() {
    let current = this.head
    while (current) {
      console.log(current.data)
      current = current.next
    }
  }
}

Complexity analysis:

Insert operation:
- Prepend at the head: O(1)
-Append at the end: O(n)
Delete operation: average O(n)
Search operation: O(n)

The main advantage of a linked list is the flexibility of insertion and deletion operations, especially insertion and deletion at known locations, which can achieve a time complexity of O(1).

2. Fiber node structure

Fiber nodes are the core data structure used internally by React to represent components. Each Fiber node corresponds to a React element, including the element's type, attributes, status and other information. Fiber nodes form a doubly linked list tree structure, which allows React to implement an interruptible rendering process.

2.1 Complete structure of Fiber node

The following is the complete structure of the Fiber node:

functionFiberNode(
  tag: WorkTag,
  pendingProps: mixed,
  key: null | string,
  mode: TypeOfMode,
) {
  //Instance
  this.tag = tag;
  this.key = key;
  this.elementType = null;
  this.type = null;
  this.stateNode = null;

  //Fiber
  this.return = null;
  this.child = null;
  this.sibling = null;
  this.index = 0;

  this.ref = null;

  this.pendingProps = pendingProps;
  this.memoizedProps = null;
  this.updateQueue = null;
  this.memoizedState = null;
  this.dependencies = null;

  this.mode = mode;

  // Effects
  this.flags = NoFlags;
  this.subtreeFlags = NoFlags;
  this.deletions = null;

  this.lanes = NoLanes;
  this.childLanes = NoLanes;

  this.alternate = null;

  // ... performance timing related code (omitted)

  // ... development environment related code (omitted)
}

2.2 Fiber node attribute explanation

Instance related
- tag: identifies Fiber node type (such as function component, class component, native DOM, etc.)
- key: unique identifier used to optimize the update process
- elementType: the type of element (such as string for DOM elements, function or class for components)
- type: similar to elementType, but may be treated specially (such as during lazy loading)
- stateNode: holds local state related to Fiber (e.g. for DOM elements, it is the actual DOM node)
Fiber tree structure
- return: points to the parent Fiber node
- child: points to the first child Fiber node
- sibling: points to the next sibling Fiber node
- index: Index in the list of child nodes of the parent node
Data related
- ref: If the element defines ref, the value of ref is stored here
- pendingProps: new pending props
- memoizedProps: props from the last rendering
- updateQueue: Queue to store status updates
- memoizedState: state when last rendered
- dependencies: dependencies (such as context, events, etc.)
Patterns and Side Effects
- mode: identifies the rendering mode of the current Fiber tree (such as Concurrent, Strict, etc.)
- flags: mark the side effects that need to be performed (such as insertion, update, deletion, etc.)
- subtreeFlags: side effect flags in subtrees
- deletions: list of child nodes to be deleted
Scheduling related
- lanes: indicates the priority of updates
- childLanes: priorities in subtrees
Others
- alternate: points to another Fiber in memory, used for double buffering

2.3 Source code for creating Fiber nodes

React uses the createFiberFromElement function to create Fiber nodes:

function createFiberFromElement(element: ReactElement, mode: TypeOfMode, lanes: Lanes): Fiber {
  let owner = null;
  if (__DEV__) {
    owner = element._owner;
  }
  const type = element.type;
  const key = element.key;
  const pendingProps = element.props;
  const fiber = createFiberFromTypeAndProps(
    type,
    key,
    pendingProps,
    owner,
    mode,
    lanes,
  );
  if (__DEV__) {
    fiber._debugSource = element._source;
    fiber._debugOwner = element._owner;
  }
  return fiber;
}

This function creates the corresponding Fiber node based on the React element, processes the element's type, key, props and other information, and creates a new Fiber object.

2.4 In-depth understanding of React elements

React elements are ordinary JavaScript objects that describe a part of the UI. They are the smallest building blocks of a React application and are used to represent what should be rendered on the interface.

2.4.1 Structure of React elements

A typical React element object structure is as follows:

const element = {
  type: 'div',
  props: {
    className: 'container',
    children: [
      { type: 'h1', props: { children: 'Hello, World!' } },
      { type: 'p', props: { children: 'This is a paragraph.' } }
    ]
  },
  key: null,
  ref: null,
  $$typeof: Symbol.for('react.element'),
  _owner: null,
  _store: {}
}

2.4.2 Main attributes of React elements

type: specifies the type of React element. It can be:
- Strings (such as 'div', 'span') represent native DOM elements
- Functions or classes represent custom React components
- React built-in components (such as React.Fragment)
props: Contains all properties passed to the component, including:
- General attributes (such as className, style, etc.)
- Special attribute children, indicating child elements
key: used to uniquely identify elements in the list, helping React to update the DOM efficiently
ref: used to obtain a reference to a DOM node or component instance
$$typeof: A Symbol used to identify this as a React element to prevent XSS attacks
_owner: used internally, pointing to the component that created the element

2.4.3 Create React elements

Typically, we use JSX to create React elements:

const element = (
  <div className="container">
    <h1>Hello, World!</h1>
    <p>This is a paragraph.</p>
  </div>
)

JSX will be translated into React.createElement() calls by tools such as Babel:

const element = React.createElement(
  'div',
  { className: 'container' },
  React.createElement('h1', null, 'Hello, World!'),
  React.createElement('p', null, 'This is a paragraph.')
)

2.4.4 Relationship between React elements and Fiber nodes

React elements are static structures that describe UI, while Fiber nodes are dynamic data structures used internally by React to manage component trees and perform updates.
Each React element will eventually correspond to a Fiber node.

3. Fiber tree structure

Fiber tree is a tree structure composed of Fiber nodes, which reflects the hierarchical relationship of React components. Fiber trees use three main pointers to build linked list structures:

child: points to the first child node
sibling: points to the next sibling node
return: points to the parent node

3.1 Fiber tree construction process

The following is a simplified Fiber tree building process:

function createFiberFromElement(element) {
  const { type, props } = element
  const fiber = new FiberNode(getFiberTag(type), props, element.key, NoMode)
  fiber.type = type
  return fiber
}

function reconcileChildrenArray(returnFiber, currentFirstChild, newChildren) {
  let prevSibling = null
  let oldFiber = currentFirstChild
  let newFiber = null
  let index = 0

  for (; index < newChildren.length; index++) {
    const newChild = newChildren[index]
    if (shouldTrackSideEffects && oldFiber && newChild && !sameNode(newChild, oldFiber)) {
      deleteChild(returnFiber, oldFiber)
    }

    if (oldFiber) {
      oldFiber = oldFiber.sibling
    }

    newFiber = createFiberFromElement(newChild)
    newFiber.return = returnFiber

    if (index === 0) {
      returnFiber.child = newFiber
    } else {
      prevSibling.sibling = newFiber
    }
    prevSibling = newFiber
  }
}

3.2 Actual code example

Consider the following React component structure:

function App() {
  return (
    <div>
      <Header />
      <Main>
        <Article />
        <Sidebar />
      </Main>
      <Footer />
    </div>
  )
}

The corresponding Fiber tree structure may be as follows:

const AppFiber = {
  tag: FunctionComponent,
  type: App,
  child:DivFiber
  // ...other properties
}

const DivFiber = {
  tag: HostComponent,
  type: 'div',
  return: AppFiber,
  child: HeaderFiber
  // ...other properties
}

const HeaderFiber = {
  tag: FunctionComponent,
  type: Header,
  return: DivFiber,
  sibling: MainFiber
  // ...other properties
}

const MainFiber = {
  tag: FunctionComponent,
  type: Main,
  return: DivFiber,
  child: ArticleFiber,
  Sibling: FooterFiber
  // ...other properties
}

const ArticleFiber = {
  tag: FunctionComponent,
  type: Article,
  return: MainFiber,
  Sibling: SidebarFiber
  // ...other properties
}

const SidebarFiber = {
  tag: FunctionComponent,
  type: Sidebar,
  return: MainFiber
  // ...other properties
}

const FooterFiber = {
  tag: FunctionComponent,
  type: Footer,
  return:DivFiber
  // ...other properties
}

This example shows how Fiber nodes are connected to each other through child, sibling and return pointers to form a complete tree structure.

4. Double buffering mechanism

The double buffering mechanism in the React Fiber architecture is a key strategy for optimizing rendering performance.

4.1 Core concepts of double buffering

current tree: The Fiber tree corresponding to the UI currently displayed on the screen.
workInProgress tree: Fiber tree used to build the next state.

Each Fiber node has an alternate property that points to the corresponding node in another tree.

4.2 Double buffer creation and update process

Initial rendering:
- React creates the current tree.
- Also creates a corresponding workInProgress tree, but does not use it.
Update Process:
- React does not create a new workInProgress tree when there is an update.
- Instead, reuse the existing workInProgress tree and update it based on the current tree.
Tree switching:
- After the update is completed, the workInProgress tree becomes the new current tree.
- The original current tree becomes the new workInProgress tree, waiting for the next update.

4.3 Source code implementation

The createWorkInProgress function in React demonstrates this mechanism:

function createWorkInProgress(current: Fiber, pendingProps: any): Fiber {
  let workInProgress = current.alternate;
  if (workInProgress === null) {
    // Create workInProgress when rendering for the first time
    workInProgress = createFiber(
      current.tag,
      pendingProps,
      current.key,
      current.mode,
    );
    workInProgress.elementType = current.elementType;
    workInProgress.type = current.type;
    workInProgress.stateNode = current.stateNode;

    workInProgress.alternate = current;
    current.alternate = workInProgress;
  } else {
    //Reuse the existing workInProgress for subsequent updates
    workInProgress.pendingProps = pendingProps;
    workInProgress.type = current.type;
    workInProgress.flags = NoFlags;
    // ...reset other properties
  }

  //Copy necessary properties
  workInProgress.child = current.child;
  workInProgress.memoizedProps = current.memoizedProps;
  workInProgress.memoizedState = current.memoizedState;
  workInProgress.updateQueue = current.updateQueue;
  // ...copy other properties

  return workInProgress;
}

4.4 Practical Example: Partial Replacement and Double Cache

Let’s walk through a concrete example to illustrate how React uses double caching and partial replacement to update the UI.

Let's say we have the following component structure:

function App() {
  const [count, setCount] = useState(0)
  return (
    <div>
      <Header />
      <Main count={count} />
      <Footer />
    </div>
  )
}

function Main({ count }) {
  return (
    <div>
      <h2>Count: {count}</h2>
      <button onClick={() => setCount(count + 1)}>Increment</button>
    </div>
  )
}

After initial rendering, the Fiber tree structure might look like this:

// current tree
const currentRoot = {
  tag: HostRoot,
  child: {
    tag: FunctionComponent,
    type: App,
    child: {
      tag: HostComponent,
      type: 'div',
      child: {
        tag: FunctionComponent,
        type: Header,
        sibling: {
          tag: FunctionComponent,
          type: Main,
          memoizedState: { count: 0 },
          sibling: {
            tag: FunctionComponent,
            type: Footer
          }
        }
      }
    }
  }
}

// workInProgress tree (initially null)
let workInProgressRoot = null

React triggers an update when the user clicks the "Increment" button. At this point, React will create or reuse the workInProgress tree:

// workInProgress tree during update
workInProgressRoot = {
  tag: HostRoot,
  child: {
    tag: FunctionComponent,
    type: App,
    child: {
      tag: HostComponent,
      type: 'div',
      child: {
        tag: FunctionComponent,
        type: Header,
        sibling: {
          tag: FunctionComponent,
          type: Main,
          memoizedState: { count: 1 }, // Pay attention to the status update here
          sibling: {
            tag: FunctionComponent,
            type: Footer
          }
        }
      }
    }
  }
}

In this process, React only needs to update the Fiber node corresponding to the Main component, and other nodes can directly reuse the nodes in the current tree. This is the embodiment of partial replacement.

After the update is complete, React swaps references to current and workInProgress:

//Exchange references
const temp = currentRoot
currentRoot = workInProgressRoot
workInProgressRoot = temp

In this way, the new current tree reflects the updated UI state, and the old current tree becomes the new workInProgress tree, waiting for the next update.

This example shows how React manages updates efficiently through double caching and partial replacement. It only modifies the necessary parts and reuses most of the existing structure.