preface

A long time ago I wrote an article about the virtual DOM, mainly explaining why Vue uses the virtual DOM and the diff algorithm of Vue. Recently, the React diff algorithm was implemented after the stack moved to React.

React version 16.9.0

React Fiber

Before learning about the React Diff algorithm, learn about React Fiber. This will help you understand the comparison between the React DiFF algorithm. After React 16, the concept of Fiber was introduced. Fiber is a re-implementation of the core algorithm. This article mainly focuses on the Diff algorithm, so Fiber can be simply understood as JS mapping of DOM structure, ignoring concepts such as sharding and update priority.

For example, the React code looks like this

class App extends React.Component {

  state = {
    list: [{
      key: 'A',
      value: 'I'm A'
    }, {
      key: 'B',
      value: 'I'm B'
    }, {
      key: 'C',
      value: 'I'm a C'
    }, {
      key: 'D',
      value: 'I'm D'
    }, {
      key: 'E',
      value: 'I'm E}}; btn2Click = () => { // }render () {
    const { list } = this.state;
    return (
    <div className="App">
      <span className="btn-2"OnClick = {this. Btn2Click} < / span > > click exchange sequence {list. The map ((item) = > (< div key = {item. Key} > {item. Value} < / div >))} < / div >)}; }Copy the code

The React Fiber mapping is abbreviated as

{ // FiberNode memoizedProps: {}, memoizedState: { list: [{// omitted here, is defined in the state list}]}, // In the Fiber tree update process, Each Fiber is a Fiber with its corresponding / / we call him a ` current < = = > workInProgress ` / / in the rendering is finished they will swap places alternate: Fiber | null, the child: {// FiberNode, for the first child of div.App elementType:"span",
    memoizedProps: {
      children: "Click reverse order",
      className: "btn-2",
      onClick: () => { }
    },
    memoizedState: null,
    return{// FiberNode corresponds to its parent FiberNode //... Omit other stateNode:'div.App'}, sibling: {// FiberNode, span.bTN-2 sibling: {// FiberNode, span.btn-2 sibling: {// FiberNode, span.bTN-2 sibling: {"div",
        child: null,
        index: 0,
        key: "A",
        memoizedProps: {
          children: "I am A",},return: {// virtual parent}, sibling: {elementType:"div",
          child: null,
          index: 0,
          key: "B",
          memoizedProps: {
            children: "I am B",},return: {// same as A, virtual parent}, sibling: {// elided, key = C, sibing key = D; D Sibing is E, end}}}, elementType: null, memoizedProps: [{$$typeof: Symbol(react.element),
        key: "A",
        props: {
          children: "I am A"
        },
        type: "div"}, {// omit other}], memoizedState: null,return{// FiberNode corresponds to its parent FiberNode //... Omit other stateNode:'div.App'
      }
    },
    stateNode: 'span.btn-2'}, sibling: null, stateNode:'div.App'// The actual div.app element}Copy the code

The complete FiberNode representation of SP.BTN-2 is captured

Use a graph to represent:

That is:

  • Each Fiber’s child points to its first child, or null if there are no children
  • Each Fiber’s sibling points to its next sibling, null if none exists
  • Each Fiber’s return points to its parent
  • Each Fiber has an index attribute indicating its order among its siblings
  • Each Fiber’s stateNode points to its native node
  • Each Fiber has a key attribute

The React diff algorithm

Given any two trees, find the least number of transformation steps. But the standard Diff algorithm requires O(n^3). Considering the situation of front-end operations — we rarely change nodes across levels, the virtual DOM only compares nodes at the same level, and its complexity is reduced to O(n). In addition, only the key and type of the nodes are compared. If they are the same, the nodes are the same

// Excerpt from updateSlotif(newChild.key === key) {// Excerpt from updateElementif (current.elementType === element.type) {
       
    } else{// Create a new node directly}}else {
return null;
}
Copy the code

Example: The nodes in the following figure change from left to right

The virtual DOM does this

A.destroy(); 
A = new A(); 
A.append(new B()); 
A.append(new C()); 
D.append(A);
Copy the code

Rather than

A.parent.remove(A);
D.append(A);
Copy the code

Example 1

How does the diff algorithm handle the operation in which the state changes from [A, B, C, D, E] to [A, F, B, C, D]? Where does Key fit into all this?

btn2Click = () => {
    this.setState({
      list: [{
        key: 'A',
        value: 'I'm A'
      }, {
        key: 'F',
        value: 'I am F
      }, {
        key: 'B',
        value: 'I'm B'
      }, {
        key: 'C',
        value: 'I'm a C'
      }, {
        key: 'D',
        value: 'I'm D'})}}]... <span className="btn-2"OnClick ={this.btn2Click}>Copy the code

If the first element A is the same and the following elements are compared in sequence with different keys, delete the BCDE after A and add FBCD. The original BCD node has not been reused at all. What does React do?

The nodes are first assembled through the reconcileChildrenArray.

functionplaceChild( newFiber: Fiber, lastPlacedIndex: number, newIndex: number, ): number { newFiber.index = newIndex; const current = newFiber.alternate; 1-1 / / tagif(current ! == null) {// mark 1-2 const oldIndex = current.index;if(oldIndex < lastPlacedIndex) {// mark 1-3 This is a move.newFiber. EffectTag = Placement;return lastPlacedIndex;
      } else{// mark 1-4 This item can stayin place.
        returnoldIndex; }}elseNewFiber. EffectTag = Placement;returnlastPlacedIndex; }}function reconcileChildrenArray(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    newChildren: Array<*>,
    expirationTime: ExpirationTime,
  ): Fiber | null {
    let resultingFirstChild: Fiber | null = null;
    let previousNewFiber: Fiber | null = null;

    let oldFiber = currentFirstChild;
    let lastPlacedIndex = 0;
    let newIdx = 0;
    letnextOldFiber = null; / / mark 1for(; oldFiber ! == null && newIdx < newChildren.length; NewIdx++) {// flag 2if (oldFiber.index > newIdx) {
        nextOldFiber = oldFiber;
        oldFiber = null;
      } else{ nextOldFiber = oldFiber.sibling; // updateSlot determines the key sum of newChildren[newIdx] and oldFibertypeIs it consistent? Returns NULL if inconsistent, or if consistentreturnPoint to thereturnConst newFiber = updateSlot(returnFiber, oldFiber, newChildren[newIdx], expirationTime, ); / / tag 4if(newFiber === null) {// No children // flag 5if(oldFiber === null) { oldFiber = nextOldFiber; } // Hit when traversing F nodebreak/ / mark sixbreak; LastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx); / / tag 8if(previousNewFiber === null) {resultingFirstChild = newFiber; }elsePreviousnewfibre.sibling = newFibre.sibling; } previousNewFiber = newFiber; oldFiber = nextOldFiber; // tag 9} // tag 10if(newIdx === newchildren.length) {// Delete the remaining old node deleteRemainingChildren(returnFiber, oldFiber);
      returnresultingFirstChild; } // mark 11if(oldFiber === null) {// Create a new nodefor (; 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;
      }
      returnresultingFirstChild; } // Add all children to a key mapfor quick lookups.
    const existingChildren = mapRemainingChildren(returnFiber, oldFiber); // mark 13 Keep scanning and use the map to restore deleted items as moves.for(; newIdx < newChildren.length; NewIdx++) {const newFiber = updateFromMap(existingChildren,returnFiber,
        newIdx,
        newChildren[newIdx],
        expirationTime,
      );
      if(newFiber ! // omit code, // 15 lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx); / / tag 16if (previousNewFiber === null) {
          resultingFirstChild = newFiber;
        } else{ previousNewFiber.sibling = newFiber; } previousNewFiber = newFiber; }} // omit the code to remove the remaining existingChildren // tag 17return resultingFirstChild;
  }
Copy the code

Follow the following process:

The assembly is the following structure:

// new first node excerpt {alternate: {// old index: 0, key:"A", sibling: { //... Old B node, sibling for C node and so on}}, index: 0, key:"A", effectTag: 0, sibling: {alternate: null, //"F",
        effectTag: 2,
        sibling: {
            alternate: {
                index: 1,
                key: "B"
            },
            index: 2,
            key: "B"// alternate sibling: {alternate: {index: 2, key:"C"
                },
                index: 3,
                key: "C",
                effectTag: 0,
                sibling: {
                    alternate: {
                        index: 3,
                        key: "D"
                    },
                    index: 4,
                    key: "D",
                    effectTag: 0,
                }
            }
        }
    }
  }
  
  // 更新节点，commitMutationEffects 中
nextEffect = {
    effectTag: 8, // 删除
    key: E,
    nextEffect: {
        effectTag: 2, // 新增
        key: F
    }
}
Copy the code

Therefore, the order of node rendering is

  1. ABCD stays fixed
  2. Deleting Node E
  3. Add node F before B

To sum up:

  • Maintain alastPlacedIndex 和 newIndex
  • lastPlacedIndex = 0, newIndex is the first node whose key or type is different from that of the old node in sequence
  • The new nodes are traversed in turn. Fetch oldIndex corresponding to the old node (if present in the old node),oldIndex < lastPlacedIndex,newFiber.effectTag = Placement, and the lastPlacedIndex remains unchanged; Otherwise, the node position remains unchanged and willlastPlacedIndex = oldIndex

Example 2

[A, B, C, D, E, A] [B, C, D, E, A

NextEffect = {effectTag: 2, // Move or add. AppendChild: natively move key: A, nextEffect: null}Copy the code
  1. lastPlacedIndex = 0, newIndex = 0
  2. NewFiber traverses node B,oldIndex = 1 > lastPlacedIndexNo operation is performed andlastPlacedIndex = oldIndex = 1
  3. lastPlacedIndex = 1, newIndex = 1
  4. NewFiber traverses C node, oldIndex = 2 > lastPlacedIndexNo operation is performed andlastPlacedIndex = oldIndex = 2`
  5. lastPlacedIndex = 2, newIndex = 2
  6. NewFiber traverses D node,oldIndex = 3 > lastPlacedIndexNo operation is performed andlastPlacedIndex = oldIndex = 3
  7. E in the same way…
  8. lastPlacedIndex = 3, newIndex = 3
  9. NewFiber traverses node A, oldIndex = 0 < lastPlacedIndex ‘, moves node A

Therefore, the order of node rendering is

  1. Move A

Example 3

[A, B, C, D, E] [A, B, C, D

  1. lastPlacedIndex = 0, newIndex = 0
  2. NewFiber traverses node E,oldIndex = 4 > lastPlacedIndexNo operation is performed andlastPlacedIndex = oldIndex = 4
  3. lastPlacedIndex = 4, newIndex = 1
  4. NewFiber traverses node A,oldIndex = 0 < lastPlacedIndexIf I move it, the lastPlacedIndex stays the same
  5. lastPlacedIndex = 4, newIndex = 2
  6. OldIndex of B is 1 < lastPlacedIndex, so move it
  7. lastPlacedIndex = 4, newIndex = 3
  8. C oldIndex is 2 < lastPlacedIndex, so move it
  9. D node…
NextEffect = {effectTag: 2, // Move or add. AppendChild: {effectTag: 2, key: B, nextEffect: {effectTag: 2, key: {effectTag: 2, key: C, nextEffect: { effectTag: 2, key: D, nextEffect: null } } } }Copy the code
  1. Move A
  2. Move the B
  3. Mobile C
  4. Mobile D

conclusion

  • Diff algorithm transforms O(N3) complexity problems into O(n)
  • The purpose of key is to reuse as many nodes as possible
  • The advantage of the virtual DOM is not that it is faster to manipulate the DOM, but that it can minimize real DOM operations by comparing the virtual DOM, refer to the documentation