Previously, I wrote an article about React Key, which mentioned Dom Diff in the Reconcile phase, but did not go into details. Today, I will explore what Dom Diff does in React.

Noun parsing

First we need to clarify the meanings of some nouns

  1. virtual dom
  2. jsx
  3. react element
  4. fiber

The Virtual DOM, which you’ve probably heard of in many articles, can be understood as a JS object describing the DOM, but it’s not a real DOM. In React, there is no such thing as a virtual DOM. Here’s Dan Abramov explaining why the word “virtual DOM” has not been used in recent years.

I wish we could retire the term “virtual DOM”. It made sense in 2013 because otherwise people assumed React creates DOM Nodes on every render. But people rarely assume this today. “Virtual DOM” sounds like a workaround for some DOM issue. React is “value UI”. Its core principle is that UI is a value, just like a string or an array. You can keep it in a variable, pass it around, use JavaScript control flow with it, And so on. That expressiveness is the point — not some diffing to avoid changes to the DOM.

In summary, virtual DOM was a new experiment in the age of manual DOM manipulation, so the name was chosen to make people aware of the changes React made. However, the react Element is used to describe the actual DOM. Its structure looks something like this: 👇🏻

{
  $$typeof: Symbol(react.element),
  key: null.props: {},
  ref: null.type: ƒ AppFunc (),_owner: null._store: {validated: false},
  _self: null._source: null 
}
Copy the code

​

Maybe you have a question, this data structure I have not seen how, it is generated, then I give another example, you will be clear 👇🏻

<AppFunc />
Copy the code

Here’s what you might write when you write React. It’s the JSX syntax we always talk about. Remember, the div here is not exactly the div in HTML. In JSX, we can write div, P, span tags, as well as our own custom functions, for example, when they are converted to react Elements, which are distinguished by the Type field.

JSX 👇 🏻 :

<div>
  <App>
    <div />
    <div />	
    <div />	
    <div />	
    <div />	
    <div />	
  </App>
</div>
Copy the code

The React Element 👇 🏻JSX 👇 🏻 :

<Yrr />
Copy the code

The React Element 👇 🏻 ​

Now that we’ve corrected vitrual Dom and clarified the relationship between JSX and react Element, we’ll focus on Fiber.

As you’ve heard, React16 changes the reconcile process from a stack structure to a Fiber structure. The goal is to support interruptible, underpinning more features in the future. Fiber has a different structure from react Element. Each React element has a corresponding Fiber node whose structure is roughly as follows: 👇🏻 ​

The content we see on the page is represented by a specific DOM tree, which has a react Element tree, and a Fiber tree, which holds props, state, and how the component should be operated. In Fiber, parent-child nodes are connected through return and child, and sibling nodes are connected through Sibling. This part is not expanded. Now that we’ve covered virtual DOM, JSX, React Element, fiber, etc., let’s return to dom Diff.

Dom Diff

Let’s start by asking ourselves these questions about Dom Diff, okay? Why? When do you compare? Compare who with whom? So what do we want to get when we compare? The reason for the comparison should be obvious, because manipulating the DOM directly is too expensive, so we need to reduce dom manipulation by “labor-saving” object comparisons.

The Diff time

So let’s be clear about the timing of Diff: Diff is only necessary when a new render is found. This is easy to understand. If you render for the first time, there is no room for optimization, and every DOM operation needs to be performed.

The Diff object

What do we have to compare when a new render happens? This is actually a comparison between the old rendered Fiber node and the new rendered React Element (we’ll see why later). The old rendered Fiber tree represents what was already on the page, while the new rendered React Element tree is what we’ll be drawing. What we do is compare these two trees to get a new Fiber tree. If it’s tree to tree, it’s O(n^3), which is obviously not what browsers can handle. React only does same-level comparisons in combination with common page changes, and the comparisons follow these two premises:

  1. Different types of nodes produce different trees;
  2. In the case of multiple nodes, key is used to make unique distinction.

Under this comparison principle, the complexity is only O(n) and covers most of the front-end page changes, ensuring correct DIFF results and greatly reducing the required time.

The Diff process

Before we explore the process, let’s answer the fourth question, what do we hope to get when we compare? Going back to the purpose of introducing DOM Diff, we wanted to find minimal changes and update pages with minimal DOM manipulation. In other words, what we want to know is which nodes need to be updated, which nodes need to be deleted, and which nodes need to be added. These operations of updating, deleting, and adding are all stored in the flag field of the Fiber node. So, the result we want is a fiber tree with its own operation tags. This explains why in step 2 we compared the old Fiber node to the newly rendered React Element.

For marking fiber, let’s give two simple examples:

  1. When we find that the react Element type is different from the original fiber type, indicating that the component type has been changed, we will add a new fiber node and label its flag field with a new label. Also label the old Fiber nodes to be removed
  2. If the react Element received the same props as the fiber props stored in the react Element in the new rendering, then the fiber node is labeled as the one that needs to be updated.

​

At a macro level, when the whole tree is traversed, we have a new Fiber tree. Some nodes are exactly the same as the old one, and some nodes are labeled as needing to be updated, deleted, or created. This is the final dom Diff output. Subsequent renderers simply adjust the DOM nodes according to the labels on Fiber to render the results on the page.

Don’t worry, don’t worry, don’t worry, don’t worry, don’t worry, don’t worry, don’t worry, don’t worry, don’t worry, don’t worry, don’t worry, don’t worry, don’t worry, don’t worry, don’t worry, don’t worry, don’t worry, don’t worry, don’t worry.

Key is a property used internally by React for Dom Diff and has higher priority than component type.

React Diff is handled differently according to the number of child nodes:

  1. New renderings, if they are a single reconcileSingleElement, are dealt with as a single reconcileSingleElement
  2. The new rendering, if it is a multi-node reconcileChildrenArray, is treated as a multi-node reconcileChildrenArray

​

Single node Diff

Let’s first observe the simple single-node diff situation, intercept a part of the source code for analysis 👇🏻As we can see, react determines the key first and then the component type, so the key takes a high priority in the Diff process

  • If the key is equal, the judgment of type will continue. If the type is equal again, the original fiber node can be reused. We will not expand it later.
  • If the keys are not equal, the old render fiber is removed and a new fiber node is generated for the new render.

​

Multi-node Diff

The react multi-node diff algorithm flows as follows :(for easy memorization, we denoted the old node as oldChildren and the new node as newChildren)

  1. For the first round of traversal, the 0th node of the old node is compared with the 0th node of the new node, in turn. If the key is different, exit the loop
  2. After completing the first round of traversal, there are several scenarios
    1. New nodes and old nodes are gone (this is the ideal case, complete the traversal, exit the diff)
    2. After traversing the new node, there are still old nodes (some old nodes still need to be processed, enter the second stage).
    3. After traversing the old nodes, there are still new nodes (some new nodes still need to be processed, entering the second stage).
    4. There are still new and old nodes (some new and old nodes need to be processed, ready to enter the second stage)
  3. To enter the second stage, the steps are as follows:
    1. Only old nodes remain: Mark all old nodes as needing to be deleted and exit diff
    2. Only new nodes remain: Create a new fiber for each node and exit the diff
    3. Both old and new nodes have surplus:
      1. Store old nodes that have not yet been paired, such as key, fiber, etc.
      2. Traverse the remaining new nodes. If they exist in the old nodes, traverse them again according to the following process:
        1. Set the lastIndex variable, starting with 0;
        2. Find the index of the old node, call it oldIndex; The index of the new node is called newIndex
        3. If oldIndex
        4. Set lastIndex to the largest of oldIndex, newIndex, lastIndex and continue traversing the next node
      3. If the new node does not exist in the old node, create a new node and label it to move to the next node

At this point, after multi-node Diff, each node knows what to do with it.

Results the Diff

Starting with the root node, diff each layer, either single-node or multi-node, depending on the node, to get the final Fiber tree we need. At this point, we can take the Fiber tree and make changes to the DOM.