In-depth analysis of the diff algorithm in React

Understanding of diff algorithm in React

diff algorithm is used to calculate the changed part of Virtual DOM , and then perform DOM operations on this part without re-rendering the entire page. The process of rendering the entire DOM structure is very expensive, and the browser needs to redraw and reflow DOM structure. The diff algorithm can update only the modified part of DOM structure during the operation without updating the entire DOM . This can minimize the operation of DOM structure and minimize the scale of browser redrawing and reflow.

Virtual DOM

The basis of the diff algorithm is Virtual DOM . Virtual DOM is a tree based on JavaScript objects. In React , it is usually compiled through JSX . Each node is called VNode , and the node is described by object properties. In fact, it is an abstraction of the real DOM . Ultimately, this tree can be mapped to the real environment through rendering operations. Simply put, Virtual DOM is a Js object that describes the entire document.
When building a page in a browser, you need to use DOM nodes to describe the entire document.

<div class="root" name="root">
    <p>1</p>
    <div>11</div>
</div>

If you use Js objects to describe the above nodes and documents, it will look like the following. Of course, this is not the object used to describe nodes in React . The source code for creating a React element in React is in react/src/ReactElement.js . The React version in this article is 16.10.2 .

{
    type: "div",
    props: {
        className: "root"
        name: "root",
        children: [{
            type: "p",
            props: {
                children: [{
                    type: "text",
                    props: {
                        text: "1"
                    }
                    
                }]
            }    
        },{
            type: "div",
            props: {
                children: [{
                    type: "text",
                    props: {
                        text: "11"
                    }
                }]
            }
        }]
    }
}

In fact, a new architecture Fiber is enabled in React16 . The core of Fiber is to implement a cyclic task scheduling algorithm based on priority and requestIdleCallback . The relevant issues are not discussed in this article. The relevant issues are roughly that the virtual DOM is transformed from a tree structure to a linked list structure. The original VDOM is a top-down tree, which is recursively traversed layer by layer through depth-first traversal. However, the biggest problem of this depth-first traversal is that it cannot be interrupted. Therefore, when we diff + patch or Mount huge nodes, it will cause a large jam. React16 's VDOM is no longer a simple tree from top to bottom, but a virtual DOM in the form of a linked list. Each node of the linked list is Fiber , not a virtual DOM node before 16 Each Fiber node records a lot of information so that it can be interrupted when it reaches a certain node. The idea of Fiber is to split the rendering/update process (recursive diff ) into a series of small tasks, check a small part of the tree each time, and see if there is time to continue the next task after it is done. If there is, continue, if not, suspend yourself and continue when the main thread is not busy. Fiber performs the following operations in diff stage, which is actually equivalent to performing priority task scheduling control in diff algorithm stage of 15 .

• Break interruptible work into smaller tasks.
• Adjust the priority of the work in progress, redo, and reuse the previous (unfinished) work.
• Task scheduling priority control in diff phase.

Comparison between operating virtual DOM and operating native DOM

I directly quote Youda's words here (the answer was from 2016-02-08 , when Vue2.0 had not yet been released. Vue2.0 was released around 2016-10-01 , Vue2.0 added virtual DOM ). The relevant link is https://www.zhihu.com/question/31809713 . It is recommended to read it in conjunction with the question in the link, and you can also look at the comparative examples in the question. In addition, the answers below are also very essential.

Native DOM operations vs. operations encapsulated by frameworks

This is a trade-off between performance vs maintainability. The purpose of the framework is to hide the underlying DOM operations for you, allowing you to describe your goals in a more declarative way, so that your code is easier to maintain. No framework can be faster than purely manual optimization of DOM operations, because DOM operation layer of the framework needs to deal with any operations that may be generated by the upper-level API , and its implementation must be universal. For any benchmark , I can write manual optimizations that are faster than any framework, but what's the point? When building an actual application, do you do manual optimization for every place? For maintainability reasons, this is obviously impossible. The guarantee given to you by the framework is that I can still provide you with decent performance without the need for manual optimization.

Misunderstandings about React's Virtual DOM

React has never said that React is faster than native DOM operations. React 's basic thinking mode is to re-render the entire application every time there is a change. If there is no Virtual DOM , it is simple to think about it as resetting innerHTML directly. Many people do not realize that in the case of a large list where all the data has changed, resetting innerHTML is actually a reasonable operation. The real problem is that under the thinking mode of re-rendering everything, even if only one line of data has changed, it also needs to reset the entire innerHTML , which is obviously a lot of waste.
We can compare the redraw performance consumption of innerHTML vs Virtual DOM :

• innerHTML : render html string O(template size) + recreate all DOM elements O(DOM size)
• Virtual DOM : render Virtual DOM + diff O(template size) + necessary DOM update O(DOM change) .

Virtual DOM render + diff is obviously slower than rendering html string, but! It is still pure js calculation, which is much cheaper than the subsequent DOM operation. You can see that the total calculation of innerHTML , whether it is js calculation or DOM operation, is related to the size of the entire interface, but among the calculation of Virtual DOM , only js calculation is related to the size of the interface, and DOM operation is related to the amount of data change. As mentioned earlier, compared with DOM operation, js calculation is extremely cheap. This is why Virtual DOM: it guarantees 1) no matter how much your data changes, the performance of each redraw is acceptable; 2) you can still use ideas similar to innerHTML to write your application.

MVVM vs Virtual DOM

Compared to React , other MVVM frameworks such as Angular, Knockout , Vue , and Avalon all use data binding : through Directive/Binding objects, observe data changes and retain references to actual DOM elements, and perform corresponding operations when there are data changes. MVVM 's change detection is at the data level, while React 's check is at the DOM structure level. The performance of MVVM also varies according to the implementation principle of change detection: Angular 's dirty check makes any change have a fixed O(watcher count) cost; Knockout/Vue/Avalon all use dependency collection, which is O(change) at both js and DOM levels:

• Dirty checking: scope digest O(watcher count) + necessary DOM update O(DOM change) .
• Dependency collection: re-collect dependencies O(data change) + necessary DOM O(DOM change) .

As you can see, the most inefficient aspect of Angular is that any small change has a performance cost related to the number of watcher . However, when all the data has changed, Angular is not actually at a disadvantage. Dependency collection needs to be re-collected during initialization and when the data changes. This cost is almost negligible when a small amount of updates are made, but it will also incur a certain amount of consumption when the amount of data is huge.
When MVVM renders a list, since each row has its own data scope, each row usually has a corresponding ViewModel instance, or a slightly lighter scope object that uses prototype inheritance, but this also has a certain cost, so the initialization of MVVM list rendering is almost certainly slower than React , because creating ViewModel / scope instances is much more expensive than Virtual DOM . A common problem for all MVVM implementations here is how to effectively reuse ViewModel instances and DOM elements that have been created when the data source of the list rendering changes, especially when the data is a brand new object. If there is no optimization for reuse, since the data is brand new, MVVM actually needs to destroy all previous instances, recreate all instances, and finally render again! This is why the angular/knockout implementations linked in the title are relatively slow. In contrast, React 's change check is at DOM structure level, so even if it is brand new data, as long as the final rendering result does not change, there is no need to do useless work.
By the way, when React renders a list, it also needs to provide a special prop called key , which is essentially the same as track-by .

Performance comparison also depends on the occasion

When comparing performance, it is important to distinguish between different scenarios such as initial rendering, small data updates, and large data updates. Virtual DOM , dirty check MVVM , and data collection MVVM have different performances and different optimization requirements in different scenarios. In order to improve the performance of small data updates, Virtual DOM also requires targeted optimization, such as shouldComponentUpdate or immutable data .

• Initial render: Virtual DOM > dirty checking >= dependency collection.
• Small data update: Dependency collection >> Virtual DOM + optimization > Dirty check (cannot be optimized) > Virtual DOM without optimization.
• Large data updates: dirty checking + optimization >= dependency collection + optimization > Virtual DOM (cannot/need not to optimize) >> MVVM without optimization.

Don't be naive to think that Virtual DOM is fast. diff is not free, batching can also be done with MVVM , and the final patch still requires the use of native API . In my opinion, the real value of Virtual DOM has never been performance, but that it 1) opens the door to functional UI programming; 2) can be rendered to backend other than DOM , such as ReactNative .

Summarize

The above comparisons are more to provide some references for framework developers and researchers. The mainstream framework + reasonable optimization is sufficient to meet the performance requirements of most applications. If there are special cases with extreme performance requirements, some maintainability should be sacrificed for manual optimization : for example, the Atom editor abandoned React in the implementation of file rendering and adopted its own tile-based rendering ; for example, on the mobile terminal, DOM-pooling virtual scrolling is required, and there is no need to consider the order change, so you can bypass the built-in implementation of the framework and make one yourself.

diff algorithm

React maintains a virtual DOM tree in memory. When the data changes ( state & props ), it will automatically update the virtual DOM to obtain a new virtual DOM tree. Then, through the Diff algorithm, it compares the old and new virtual DOM trees to find the smallest changed part, adds the changed part Patch to the queue, and finally updates these Patch to the actual DOM in batches.

Time Complexity

First of all, a complete diff requires O(n^3) time complexity, which is a minimum edit distance problem. When comparing the minimum edit distance of strings, the time complexity of using dynamic programming is O(mn) . However, DOM is a tree structure, and the time complexity of the minimum edit distance problem of the tree structure has evolved from O(m^3n^3) to O(n^3) in more than 30 years of evolution. If you are interested in this issue, you can study the paper https://grfia.dlsi.ua.es/ml/algorithms/references/editsurvey_bille.pdf .
For the diff algorithm that was originally introduced to improve efficiency, using a time complexity of O(n^3) is obviously not appropriate. If there are 1000 node elements, one billion comparisons will be required. This is an expensive algorithm, so there must be some compromises to speed up the process. The comparison is simplified through some strategies, and the time complexity is reduced to O(n) . Although it is not the minimum edit distance, it is a better solution as a comprehensive consideration of edit distance and time performance, and it is a better compromise.

diff strategy

O(n) time complexity mentioned above is achieved through a certain strategy. React documentation mentions two assumptions:

• Two elements of different types will produce different trees.
• By attaching a key attribute to the renderer, developers can indicate which child elements may be stable.

In simple terms:

• Only comparisons at the same level are performed, and cross-level moves are considered creation and deletion operations.
• If the elements are of different types, a new element is considered to be created and their children are not recursively compared.
• If the content is similar, such as list elements, key can be used to uniquely determine whether it is a move, create, or delete operation.

After the comparison, several situations will occur, and then corresponding operations will be performed:

• This node is added or removed -> Add or remove new nodes.
• Attributes are changed -> old attributes are changed to new attributes.
• The text content is changed -> the old content is changed to the new content.
• Whether the node tag or key changes- -> If changed, remove it and create a new element.

analyze

In the analysis, we will briefly quote the source code of React , which plays an auxiliary role. The actual source code is very complicated, and we quote some fragments to help us understand it. The source code TAG of this article is 16.10.2 .
The code related to if (__DEV__){...} is actually written for a better developer experience. Friendly error reporting, render performance testing and other codes in React are all written in if (__DEV__) . These codes will not be packaged during production build , so we can provide code dedicated to developers without any worries. One of the best practices of React is to use development build during development and production production build in production environment, so we can actually skip this part of the code and focus on understanding the more core parts.
Our analysis of diff algorithm starts from reconcileChildren . We will not introduce the related parts from setState -> enqueueSetState(UpdateQueue) -> scheduleUpdate -> performWork -> workLoop -> beginWork -> finishClassComponent -> reconcileChildren in detail. It should be noted that beginWork will diff each Fiber one by one, and the period is interruptible, because each time the next Fiber is compared, it will first determine whether the remaining time of this frame is sufficient. Each node of the linked list is Fiber , not a virtual DOM node before 16 Each Fiber has a React16 diff strategy that uses an algorithm that starts comparing from the head of the linked list. It is a chain-like depth-first traversal, that is, it has changed from a tree structure to a linked list structure, which is actually equivalent to priority task scheduling control in diff algorithm stage of 15 . In addition, each Fiber has three attributes: child , sibling , and return which serve as pointers to the front and back of the link tree; child is a structural pointer that simulates the tree structure; effectTag is a very interesting tag that is used to record the type of effect . effect refers to the way of operating DOM , such as modification, deletion, and other operations, which are used to commit later (similar to a database); firstEffect , lastEffect , etc. are used to save the status of effect before and after the interruption, and the user can restore the previous operation after the interruption, and tag is used for marking.
reconcileChildren implements the widely circulated Virtul DOM diff , which is actually just an entry function. If it is the first rendering, current is null , and Fiber instance of the child node is created through mountChildFibers . If it is not the first rendering, reconcileChildFibers is called to do diff , and then effect list is obtained.

// react-reconciler/src/ReactChildFiber.js line 1246
export function reconcileChildren(
  current: Fiber | null,
  workInProgress: Fiber,
  nextChildren: any,
  renderExpirationTime: ExpirationTime,
) {
  if (current === null) { // First render creates a child node's `Fiber` instance workInProgress.child = mountChildFibers(
      workInProgress,
      null,
      nextChildren,
      renderExpirationTime,
    );
  } else { // Otherwise call `reconcileChildFibers` to do `diff`
    workInProgress.child = reconcileChildFibers(
      workInProgress,
      current.child,
      nextChildren,
      renderExpirationTime,
    );
  }
}

Comparing the differences between mountChildFibers and reconcileChildFibers , we can see that they both come from the ChildReconciler factory function, but the parameters passed are different. This parameter is called shouldTrackSideEffects . Its function is to determine whether to add some effectTag . It is mainly used to optimize the initial rendering because there is no update operation in the initial rendering. ChildReconciler is a super long factory (wrapper) function with many helper functions inside. The function finally returned is called reconcileChildFibers , which implements reconciliation of child fiber nodes.

// react-reconciler/src/ReactChildFiber.js line 1370
export const reconcileChildFibers = ChildReconciler(true);
export const mountChildFibers = ChildReconciler(false);

function ChildReconciler(shouldTrackSideEffects) { 
  // ...
  function deleteChild(){
      // ...
  }
  function useFiber(){
      // ...
  }
  function placeChild(){
      // ...
  }
  function placeSingleChild(){
      // ...
  }
  function updateTextNode(){
      // ...
  }
  function updateElement(){
      // ...
  }
  function updatePortal(){
      // ...
  }
  function updateFragment(){
      // ...
  }
  function createChild(){
      // ...
  }
  function updateSlot(){
      // ...
  }
  function updateFromMap(){
      // ...
  }
  function warnOnInvalidKey(){
      // ...
  }
  function reconcileChildrenArray(){
      // ...
  }
  function reconcileChildrenIterator(){
      // ...
  }
  function reconcileSingleTextNode(){
      // ...
  }
  function reconcileSingleElement(){
      // ...
  }
  function reconcileSinglePortal(){
      // ...
  }
  function reconcileChildFibers(){
      // ...
  }
  return reconcileChildFibers;
}

reconcileChildFibers is the main code of diff part. The related operations are all in the ChildReconciler function. The relevant parameters in this function are: returnFiber is the parent node of the layer to be diff , currentFirstChild is the first Fiber node of the current layer, and newChild is the vdom node to be updated (which may be TextNode , ReactElement , or an array), not a Fiber node. expirationTime is the expiration time. This parameter is related to scheduling and has little to do with diff . In addition, it should be noted that reconcileChildFibers is a layer structure of reconcile(diff) .

First, let's look at TextNode diff , which is the simplest. There are two cases for diff TextNode :

• currentFirstNode is TextNode .
• currentFirstNode is not TextNode .

There are two cases because of node reuse. In the first case, xxx is a TextNode , which means that this node can be reused. Reused nodes are very helpful for performance optimization. Since the new child has only one TextNode , the remaining aaa node can be deleted after reusing the node, and child of div can be added to workInProgress . useFiber is a method for reusing nodes, deleteRemainingChildren is a method for deleting remaining nodes. Here, deletion starts from currentFirstChild.sibling .

if (currentFirstChild !== null && currentFirstChild.tag === HostText) {
  // We already have an existing node so let's just update it and delete
  // the rest.
  deleteRemainingChildren(returnFiber, currentFirstChild.sibling); // Delete siblings const existing = useFiber(currentFirstChild, textContent, expirationTime);
  existing.return = returnFiber;
  return existing; // reuse }

In the second case, xxx is not a TextNode , which means that this node cannot be reused, so the remaining nodes are deleted starting from currentFirstChild . createFiberFromText is a method to create nodes based on textContent . In addition, deleting a node will not actually delete the node from the linked list, but only add a delete tag , and it will be actually deleted when commit is made.

// The existing first child is not a text node so we need to create one
// and delete the existing ones.
// Create a new Fiber node and delete the old node and its brothers deleteRemainingChildren(returnFiber, currentFirstChild);
const created = createFiberFromText(
  textContent,
  returnFiber.mode,
  expirationTime,
);

Next is diff of React Element . At this time, we are dealing with the situation where the parent node of the node is only this node. Similar to diff of TextNode above, their ideas are the same. First, find out if there is a node that can be reused. If not, create another one. At this time, the above two assumptions will be used to determine whether the node can be reused, that is, whether key is the same and whether the node type is the same. If the above are the same, it can be considered that the node has only changed its content and there is no need to create a new node, so it can be reused. If the nodes are of different types, delete the remaining nodes starting from the current node. When searching for reusable nodes, it does not only focus on whether the first node is reusable, but continues to loop in the layer to find a reusable node. The top-level while and the bottom child = child.sibling; are to continue to find a reusable node with the same key and tag from the child nodes. In addition, deleting a node will not actually delete the node from the linked list, but only add a delete tag , and it will be actually deleted when commit is made.

// react-reconciler/src/ReactChildFiber.js line 1132
const key = element.key;
let child = currentFirstChild;
while (child !== null) {
  // TODO: If key === null and child.key === null, then this only applies to
  // the first item in the list.
  if (child.key === key) {
    if (
      child.tag === Fragment
        ? element.type === REACT_FRAGMENT_TYPE
        : child.elementType === element.type ||
          // Keep this check inline so it only runs on the false path:
          (__DEV__
            ? isCompatibleFamilyForHotReloading(child, element)
            : false)
    ) {
      deleteRemainingChildren(returnFiber, child.sibling); // Because the current node has only one node, and the old one has sibling nodes that need to be deleted, which is redundant const existing = useFiber(
        child,
        element.type === REACT_FRAGMENT_TYPE
          ? element.props.children
          : element.props,
        expirationTime,
      );
      existing.ref = coerceRef(returnFiber, child, element);
      existing.return = returnFiber;
      // ...
      return existing;
    } else {
      deleteRemainingChildren(returnFiber, child);
      break;
    }
  } else {
    deleteChild(returnFiber, child); // Start deleting from child
  }
  child = child.sibling; // Continue to find a reusable node from the child nodes}

The next step is to create a node because no reusable node is found. The way to create Fragment node is different from that of a general Element node, because Fragment is originally a meaningless node. Fiber it really needs to create is its children , not itself. Therefore, createFiberFromFragment passes element.props.children instead of element .

// react-reconciler/src/ReactChildFiber.js line 1178
if (element.type === REACT_FRAGMENT_TYPE) {
  const created = createFiberFromFragment(
    element.props.children,
    returnFiber.mode,
    expirationTime,
    element.key,
  );
  created.return = returnFiber;
  return created;
} else {
  const created = createFiberFromElement(
    element,
    returnFiber.mode,
    expirationTime,
  );
  created.ref = coerceRef(returnFiber, currentFirstChild, element);
  created.return = returnFiber;
  return created;
}

diff Array is the most complicated part of diff , and a lot of optimizations have been done. Because Fiber tree is a single linked list structure, there is no data structure such as a child node array, and there is no tail cursor for simultaneous comparison of both ends. Therefore, the React algorithm is a simplified double-ended comparison method, which only compares from the head. diff algorithm in Vue2.0 is directly implemented using the double-ended comparison method when patch .
First, consider comparing the same positions. This is a relatively easy way to think of. That is, when doing diff , you can compare the new and old arrays one by one according to the index. If it can be reused, delete this node from the old linked list. If it cannot be reused, use other reuse strategies. At this time, newChildren array is a VDOM array, so updateSlot is used here to package it into newFiber .

// react-reconciler/src/ReactChildFiber.js line 756
function reconcileChildrenArray(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    newChildren: Array<*>,
    expirationTime: ExpirationTime,
  ): Fiber | null {
    // Machine translation comments // This algorithm cannot be optimized by searching at both ends, because we don't have back pointers on the fiber. I wanted to see how far we could go with this model. If it ends up not being worth the tradeoff, we can always add it back later.
    // Even with dual-end optimizations, we want to optimize when there are few changes and force a comparison instead of looking for a map. It wants to explore to get to that path first in forward mode, and only go to the map when we notice we need to look ahead a lot. This doesn't handle reversals as well as two ended searches, but that's unusual. Furthermore, to make both ends optimization work on Iterables, we need to copy the entire collection.
    // In the first iteration, we just hit the bad case (adding everything to the map) on every insert/move.
    // If you change this code, you also need to update reconcileChildrenIterator(), which uses the same algorithm.
    let oldFiber = currentFirstChild;
    let lastPlacedIndex = 0;
    let newIdx = 0;
    let nextOldFiber = null;
     // The first for loop compares the new and old nodes one by one according to the index. When the new and old nodes are inconsistent, the loop is exited and the node and oldFiber node at the time of exit are recorded for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
      if (oldFiber.index > newIdx) { // Position mismatch nextOldFiber = oldFiber; // Next old node to be compared oldFiber = null; // If newFiber is also null (cannot be reused), exit the current one-to-one comparison for loop} else {
        nextOldFiber = oldFiber.sibling; //Under normal circumstances, for the next cycle, get the value of the sibling node and assign it to oldFiber
      }
      // //If the node can be reused (key value matches), update and return the new node, otherwise return null, indicating that the node cannot be reused const newFiber = updateSlot( // Determine whether the node can be reused returnFiber,
        oldFiber,
        newChildren[newIdx],
        expirationTime,
      );
      // The node cannot be reused to jump out of the loop if (newFiber === null) { 
        // TODO: This breaks on empty slots like null children. That's
        // unfortunate because it triggers the slow path all the time. We need
        // a better way to communicate whether this was a miss or null,
        // boolean, undefined, etc.
        if (oldFiber === null) {
          oldFiber = nextOldFiber; // Record nodes that cannot be reused and exit comparison}
        break; // exit the loop }
      if (shouldTrackSideEffects) {
        // If you don't reuse existing nodes, delete the existing nodes if (oldFiber && newFiber.alternate === null) {
          // We matched the slot, but we didn't reuse the existing fiber, so we
          // need to delete the existing child.
          deleteChild(returnFiber, oldFiber);
        }
      }
      // This traversal will mark the newly added nodes as inserted lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      if (previousNewFiber === null) {
        // TODO: Move out of the loop. This only happens for the first run.
        resultingFirstChild = newFiber;
      } else {
        // TODO: Defer siblings if we're not at the right index for this slot.
        // Ie if we had null values ​​before, then we want to defer this
        // for each null value. However, we also don't want to call updateSlot
        // with the previous one.
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
      oldFiber = nextOldFiber; // Reassign oldFiber and continue traversal}

updateSlot method defines whether it can be reused. For text nodes, if key is not null , it means that the old node is not TextNode , and the new node is TextNode , so null is returned and it cannot be reused. Otherwise, it can be reused. Call the updateTextNode method. Note that updateTextNode contains the logic of the first rendering. During the first rendering, a TextNode will be inserted instead of being reused.

// react-reconciler/src/ReactChildFiber.js line 544
function updateSlot(
    returnFiber: Fiber,
    oldFiber: Fiber | null,
    newChild: any,
    expirationTime: ExpirationTime,
  ): Fiber | null {
    // Update the fiber if the keys match, otherwise return null.

    const key = oldFiber !== null ? oldFiber.key : null;

    if (typeof newChild === 'string' || typeof newChild === 'number') {
      // For new nodes, if they are strings or numbers, they do not have keys.
      // If the old node has a key, it cannot be reused and returns null directly.
      // If the old node key is null, it means the old node is a text node, so you can reuse if (key !== null) {
        return null;
      }
      return updateTextNode(
        returnFiber,
        oldFiber,
        '' + newChild,
        expirationTime,
      );
    }

    // ...

    return null;
}

When newChild is Object , it is basically similar to diff of ReactElement , except that there is no while . It determines whether the type of key and element is equal to determine whether it can be reused. First, to determine whether it is an object, use typeof newChild === object && newChild!== null . Note that !== null should be added because typeof null is also object . Then, use $$typeof to determine whether it is REACT_ELEMENT_TYPE or REACT_PORTAL_TYPE , and call different reuse logics respectively. Since arrays are also Object , there is also array reuse logic in this if .

// react-reconciler/src/ReactChildFiber.js line 569
if (typeof newChild === 'object' && newChild !== null) {
  switch (newChild.$$typeof) {
    case REACT_ELEMENT_TYPE: { // ReactElement 
      if (newChild.key === key) {
        if (newChild.type === REACT_FRAGMENT_TYPE) {
          return updateFragment(
            returnFiber,
            oldFiber,
            newChild.props.children,
            expirationTime,
            key,
          );
        }
        return updateElement(
          returnFiber,
          oldFiber,
          newChild,
          expirationTime,
        );
      } else {
        return null;
      }
    }
    case REACT_PORTAL_TYPE: {
      //Call updatePortal
      // ...
    }
  }

  if (isArray(newChild) || getIteratorFn(newChild)) {
    if (key !== null) {
      return null;
    }

    return updateFragment(
      returnFiber,
      oldFiber,
      newChild,
      expirationTime,
      null,
    );
  }
}

Let's go back to the initial traversal. When we complete the traversal, there will be two situations, that is, the old nodes have been traversed, or the new nodes have been traversed. If we have traversed the new nodes at this time, that is, there is nothing to update, this situation generally means that the elements are deleted from the original array, then just delete the remaining old nodes. If the old nodes are reused in the first cycle, but there are new nodes, it is very likely that new nodes have been added. In this case, you only need to create Fiber directly based on the remaining new nodes.

// react-reconciler/src/ReactChildFiber.js line 839
// The new node has been updated, delete the redundant old nodes if (newIdx === newChildren.length) {
  // We've reached the end of the new children. We can delete the rest.
  deleteRemainingChildren(returnFiber, oldFiber);
  return resultingFirstChild;
}

// The new node has been updated, delete the redundant old nodes if (oldFiber === null) {
  // If we don't have any more existing children we can choose a fast path
  // since the rest will all be insertions.
  for (; newIdx < newChildren.length; newIdx++) {
    const newFiber = createChild(
      returnFiber,
      newChildren[newIdx],
      expirationTime,
    );
    if (newFiber === null) {
      continue;
    }
    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
    if (previousNewFiber === null) {
      // TODO: Move out of the loop. This only happens for the first run.
      resultingFirstChild = newFiber;
    } else {
      previousNewFiber.sibling = newFiber;
    }
    previousNewFiber = newFiber;
  }
  return resultingFirstChild;
}

Next, consider how to reuse nodes in the case of movement, that is, if the old array and the new array both have this element and the position is different, React puts all the old array elements in Map according to key or index , and then traverses the new array, and quickly finds out whether there is any reusable element in the old array according to the key or index of the new array. If the element has key , the Map key is stored in key , otherwise index key stored.

// react-reconciler/src/ReactChildFiber.js line 872
// Add all children to a key map for quick lookups.
// Add the key or index of the existing node to the map structure starting from oldFiber const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

// Keep scanning and use the map to restore deleted items as moves.
// For the remaining new nodes that have not been compared, compare them one by one in the map of the old nodes by key or index to see if they can be reused.
for (; newIdx < newChildren.length; newIdx++) {
  // Mainly check whether the key or index of the new and old nodes are the same, and then check whether they can be reused.
  const newFiber = updateFromMap(
    existingChildren,
    returnFiber,
    newIdx,
    newChildren[newIdx],
    expirationTime,
  );
  if (newFiber !== null) {
    if (shouldTrackSideEffects) {
      if (newFiber.alternate !== null) {
        // The new fiber is a work in progress, but if there exists a
        // current, that means that we reused the fiber. We need to delete
        // it from the child list so that we don't add it to the deletion
        // list.
        existingChildren.delete( // Delete the key or index of the reused node in the map
          newFiber.key === null ? newIdx : newFiber.key,
        );
      }
    }
    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
    // Add newFiber to the updated newFiber structure.
    if (previousNewFiber === null) {
      resultingFirstChild = newFiber;
    } else {
      previousNewFiber.sibling = newFiber;
    }
    previousNewFiber = newFiber;
  }
}

// react-reconciler/src/ReactChildFiber.js line 299
// Save the key or index of the old node and the old node to the map structure, so that it is convenient to obtain by key or index function mapRemainingChildren(
    returnFiber: Fiber,
    currentFirstChild: Fiber,
  ): Map<string | number, Fiber> {
    // Add the remaining children to a temporary map so that we can find them by
    // keys quickly. Implicit (null) keys get added to this set with their index
    // instead.
    const existingChildren: Map<string | number, Fiber> = new Map();

    let existingChild = currentFirstChild;
    while (existingChild !== null) {
      if (existingChild.key !== null) {
        existingChildren.set(existingChild.key, existingChild);
      } else {
        existingChildren.set(existingChild.index, existingChild);
      }
      existingChild = existingChild.sibling;
    }
    return existingChildren;
  }

At this point, the new array traversal is completed, that is, the diff process at the same layer is completed. We can divide the whole process into three stages:

• First, traverse the new array and compare the new and old arrays with the same index . Use updateSlot method to find nodes that can be reused. Exit the loop until a node that cannot be reused is found.
• After the first traversal is completed, the remaining old nodes are deleted and the remaining new nodes are appended. If the new nodes have been traversed, the remaining old nodes are deleted in batches ; if the old nodes are traversed and there are still new nodes remaining, the new nodes are directly inserted.
• Put all the old array elements in Map by key or index , then traverse the new array and insert the elements of the old array. This is the case of moving.

Daily Question

https://github.com/WindrunnerMax/EveryDay

refer to

https://zhuanlan.zhihu.com/p/89363990
https://zhuanlan.zhihu.com/p/137251397
https://github.com/sisterAn/blog/issues/22
https://github.com/hujiulong/blog/issues/6
https://juejin.cn/post/6844904165026562056
https://www.cnblogs.com/forcheng/p/13246874.html
https://zh-hans.reactjs.org/docs/reconciliation.html
https://zxc0328.github.io/2017/09/28/react-16-source/
https://blog.csdn.net/halations/article/details/109284050
https://blog.csdn.net/susuzhe123/article/details/107890118
https://github.com/Advanced-Frontend/Daily-Interview-Question/issues/47
https://github.com/jianjiachenghub/react-deeplearn/blob/master/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/React16%E6%BA%90%E7%A0%81%E8%A7%A3%E6%9E%906-Fiber%E9%93%BE%E5%BC%8Fdiff%E7%AE%97%E6%B3%95.md

The above is a detailed analysis of the diff algorithm in React. For more information about the diff algorithm in React, please pay attention to other related articles on 123WORDPRESS.COM!