React's reconciliation algorithm Diffing algorithm strategy detailed explanation

Algorithmic Strategy

React's reconciliation algorithm mainly occurs in the render stage. The reconciliation algorithm is not a specific algorithm function, but refers to a strategy adopted in the reconciliation process to improve the performance of building the workInProcess tree and the performance of updating the Dom tree, also known as the diffing algorithm. When describing the "Diffing" algorithm on React's official website, it mentions "diffing two trees", but when implementing the source code, it does not create two trees and then diffing the two trees from top to bottom. This diffing occurs when building child nodes, which is actually the diffing of the newly generated ReactElement and the fibe node on the current tree. In order to keep the time complexity of the diffing algorithm within O(n) (the time complexity of tree diff involves the edit distance of the tree, see here), the following strategy is adopted:

Only compare nodes at the same level (seemingly this is not mentioned on the official website)

For single node comparison, if the current node type and key are not the same, no longer compare its child nodes, directly delete the node and its entire subtree, and regenerate the node tree according to ReactElement. Because React believes that different types of components generate different tree structures and do not need to be reused.

If the child nodes are arrays, the nodes can be located and compared based on the unique key value, so that even if the order of the child nodes changes, they can be reused based on the key value.

It is worth noting that all node diffing will compare the key, and the default value of key is null. If not set, null is always equal to null, and the key is considered to be the same.

Single-node diffing

When a single node is diffed, two sets of attributes are diffed: fibe.elementType vs ReactElement.type, fibe.key vs ReactElement.key. If these two sets of attributes are equal, the physical space of the data structure will have the following reuse logic (see the source code reconcileSingleElement function for details):

1. If the current fibe has an alternate node (which means that this fibe node has participated in the reconciliation before), the physical space of the alternate node is reused; otherwise, the current fibe node needs to be cloned to occupy a new physical space.
2. The corresponding instance or Dom will be reused
3. The child tree under the current fibe will also be mounted directly (it will be used when recursing child nodes in the next step)

If one of the two sets of attributes is not equal:

• fibe is recreated based on ReactElement
• The corresponding instance and Dom will also be rebuilt
• Delete all child trees.

If the generated ReactElement is a single node, but the corresponding current tree has multiple nodes, it will search one by one to see if there is a match. If a match is found, the others will be deleted; if no match is found, all will be deleted. For example, the Couter component has the following logic: when the number of clicks is greater than 10, hide the click button. When it reaches the 10th time, the span node will be reused.

class Counter extends React.Component {
    state={
        count:0
    }
    addCount = ()=>{
        const count = this.state.count+1;
        this.setState({count})
    }
    componentDidUpdate(){
        console.log("updated")
    }
    render(){
        return this.state.count < 10 ? [
            <button onClick={this.addCount}>Click</button>
            <span>Number of clicks: {this.state.count}</span>
        ]:<span>Number of clicks: {this.state.count}</span>;
    }
}

Array node diffing

When diffing array nodes, the process is more complicated: (see the reconcileChildrenArray function for the source code)

There are two important traversals in the middle. The first one is traversal by index, comparing the new and old nodes in turn, and immediately interrupting the traversal if a key value mismatch is encountered. In the second traversal, a "key - node" Map table is created for the remaining old nodes, and the remaining new nodes are traversed, and the old nodes are searched from the table according to the key value for comparison. The following are the matching and comparison of new and old nodes in three cases.

Key value usage requirements

From the perspective of diffing single nodes and array nodes, the key value is mainly used to reduce new creation. To ensure that the new and old nodes can match during diffing, the following points should be noted when using key values:

1. It must be stable. If the key value changes every time (for example, a random number is used), the new and old sections will not match during diffing, which will cause a large number of new creations.
2. It must be unique. If the key value is not unique, it will be missed and confused when creating the "key - node" Map table, resulting in page update errors.

For a single node, the key value is also used during diffing. Don't think it is useless and set it randomly. There are also some non-standard usages, which use key values ​​​​for a single node to achieve component destruction and reconstruction, but this usage is not in line with the design concept of React.

For example, there is a log component that pulls log data internally and has no external data dependencies . However, when the requirements are iterated, an approval operation is added to the same page. After approval, a new log data will be added to the backend. At this time, you will want the front-end page to display the newly added log data in real time, and you will need to trigger the log component to pull the data again. If you do not use the method of promoting data upward to solve the problem, you can assign a random key to the component. When the approval operation is completed, modify the key value and the component will be rebuilt. However, this method has high overhead, and the entire component tree will be destroyed and rebuilt. Other solutions can be used instead. For example, you can specify a ref for the component. When the approval is completed, call the refresh function of the component through the ref to re-acquire the data and update the component.

For array nodes, the key value plays a key role mainly when there is a large misalignment in the position of the child node . For ordinary additions and deletions at the end, the first index traversal can complete the matching and will not enter the second key map traversal. Because the key value pair must be "stable" and "unique", the front end generally requires the back end to provide a unique identifier for the list data. For the aggregation interface, this will add extra work to the back end. In this case, you can first understand the changing characteristics of the data and then decide whether you really need to set the key.

For the log component above, the log is a list. Newly added logs are inserted in the first line. If the key is not set, basically all child nodes need to be updated. If a key is set, the backend service needs to add a "forever" unique identifier, such as an id, to each log. I once experienced a case where the page display was incorrect when the data was updated because the uniqueness of the key value changed.

This is the end of this article about React's reconciliation algorithm (Diffing algorithm). For more relevant React Diffing algorithm content, please search 123WORDPRESS.COM's previous articles or continue to browse the following related articles. I hope everyone will support 123WORDPRESS.COM in the future!