React source code is used in a lot of algorithm tricks, mainly including bit operations, depth first traversal, linked list operations, stack operations, heap sort, etc. This article based on [email protected], comb out React source depth first traversal (DFS) use skills.

For searching (or traversing) tree or graph structures, there are depth first (DFS) and breadth first (BFS).

concept

Depth-first traversal: DFS(English :Depth- first-search,DFS) is an algorithm for traversing or searching trees or graphs.

When all edges of node V have been explored, the search will go back to the starting node of the edge where node V was found. This process continues until all nodes reachable from the source node have been discovered. If there are still undiscovered nodes, select one of them as the source node and repeat the process until all nodes are accessed.

implementation

There are two mainstream implementations of DFS.

  1. Recursion (simple)
  2. usingThe stackStore the traversal path
function Node() {
  this.name = ' ';
  this.children = [];
}

function dfs(node) {
  console.log('Exploratory stage:', node.name);
  node.children.forEach(child= > {
    dfs(child);
  });
  console.log('Backtracking phase:', node.name);
}
Copy the code
  1. Use the stack
function Node() {
  this.name = ' ';
  this.children = [];

  // Since we want to distinguish between the search phase and the traceback phase, we must have an attribute that records whether the node has been visited
  // This attribute is not required if search and backtracking are not printed
  this.visited = false;
}

function dfs(node) {
  const stack = [];
  stack.push(node);
  // If the top element still exists, the loop continues
  while ((node = stack[stack.lenth - 1]) {if (node.visited) {
      console.log('Backtracking phase:', node.name);
      // Traceback completed to pop the element
      stack.pop();
    } else {
      console.log('Exploratory stage:', node.name);
      node.visited = true;
      // Take advantage of the advanced feature of the stack to feed nodes into the stack in reverse order
      for (let i = node.children.length - 1; i >= 0; i--) { stack.push(node.children[i]); }}}}Copy the code

Use scenarios in React

Depth-first traversal is typically used in React, mostly during ReactElement and fiber tree construction. Second, when using a context, the node that consumes the context needs to be looked up depth-first.

ReactElement “tree” construction

ReactElement is not a strict tree structure. For convenience, it is called a tree.

In the React-Reconciler package, the construction process of ReactElement is actually a reconciler reconciliation process. The construction of the fiber tree is carried out alternately and step by step (read in detail in the Fiber Tree construction section, this section only describes the use scenario of depth-first traversal).

The construction of the ReactElement tree is actually the sum of all levels of component Render. The whole process is embodied in the Reconciler work cycle.

The source code is in reactFiberWorkloop.js, where the dFS-independent side-logic has been removed for simplicity.

function workLoopSync() {
  // 1. The outermost loop ensures that each node can be traversed without missing
  while(workInProgress ! = =null) { performUnitOfWork(workInProgress); }}function performUnitOfWork(unitOfWork: Fiber) :void {
  const current = unitOfWork.alternate;
  let next;
  // 2
  next = beginWork(current, unitOfWork, subtreeRenderLanes);
  if (next === null) {
    // 3. CompleteUnitOfWork is the backtracking phase
    completeUnitOfWork(unitOfWork);
  } else{ workInProgress = next; }}function completeUnitOfWork(unitOfWork: Fiber) :void {
  let completedWork = unitOfWork;
  do {
    const current = completedWork.alternate;
    const returnFiber = completedWork.return;
    let next;
    // 3.1 Traceback and process nodes
    next = completeWork(current, completedWork, subtreeRenderLanes);
    if(next ! = =null) {
      // Determine whether a new node is derived during processing
      workInProgress = next;
      return;
    }
    const siblingFiber = completedWork.sibling;
    // 3.2 Determine whether there are side branches
    if(siblingFiber ! = =null) {
      workInProgress = siblingFiber;
      return;
    }
    // 3.3 Continue backtracking without side effects
    completedWork = returnFiber;
    workInProgress = completedWork;
  } while(completedWork ! = =null);
}
Copy the code

The above source code is essentially a recursive approach to DFS, assuming the following component structure:

class App extends React.Component {
  render() {
    return (
      <div className="app">
        <header>header</header>
        <Content />
        <footer>footer</footer>
      </div>); }}class Content extends React.Component {
  render() {
    return (
      <React.Fragment>
        <p>1</p>
        <p>2</p>
        <p>3</p>
      </React.Fragment>); }}export default App;
Copy the code

The traversal path can be drawn as follows:

Note:

  • ReactElementThe tree is in a big loopbeginWorkStages are generated “step by step”.
  • Each level in “step by step” is a valueclassorfunctionType of component, each time calledrenderOr execute it oncefunctionCall, will generate a batchReactElementNode.
  • ReactElementThe construction of the tree is actually the components at all levelsrenderThe sum after that.

Structure of fiber tree

In the construction process of ReactElement, along with the construction of fiber tree, fiber tree is also generated in the beginWork stage.

Draw the traversal path as follows:

Find the consumption node of the context

When the context changes, you need to find all the child nodes that depend on the context (more on that in the Context Principles section), which is also a DFS, the source code is in ReactFiberNewContext.js.

Stripping out the backbone logic, it is clear that the loop recursion is used to iterate:

export function propagateContextChange(workInProgress: Fiber, context: ReactContext
       
        , changedBits: number, renderLanes: Lanes,
       ) :void {
  let fiber = workInProgress.child;
  while(fiber ! = =null) {
    let nextFiber;
    // Visit this fiber.
    const list = fiber.dependencies;
    if(list ! = =null) {
      // Match logic such as context, which is independent of DFS
      // ...
    } else {
      // Look downnextFiber = fiber.child; } fiber = nextFiber; }}Copy the code

conclusion

Since React internally uses two large trees, ReactElement and fiber, there is a lot of logic about node access.

This section focuses on the concept of DFS and its use in the React source code. Among them, DFS traversal of Fiber tree involves many codes and is widely distributed, covering most of the work in the Reconciler stage, and is the core process of the work cycle in the Reconciler stage.

In addition to DFS, there is a lot of logic in the source code to find nodes in the tree (e.g., looking up the parent node, etc.). The tree structure traversal is a high proportion of the source code, understanding these algorithm techniques can better understand the React source code.

The resources

Depth-first search

Write in the last

This article belongs to the diagram react principle series algorithm plate, this series of nearly 20 articles, not for the interview, really is to understand the React source code, and then improve the architecture and coding ability. You are welcome to learn React source code.