React diff algorithm source code analysis

  // Single node comparison function reconcileSingleElement(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    element: ReactElement,
    lanes: Lanes,
  ): Fiber {
    // The key of the new reactElement
    const key = element.key;
    //Current child fiber node let child = currentFirstChild;
    while (child !== null) {
      // Only diff if the key is the same
      if (child.key === key) {
        switch (child.tag) {
          // ...
          default: {
            // If the current fiber and reactElement have the same type, then if (child.elementType === element.type) {
              // Delete other nodes at the same level deleteRemainingChildren(returnFiber, child.sibling);
              // Reuse the current child fiber
              const existing = useFiber(child, element.props);
              existing.ref = coerceRef(returnFiber, child, element);
              existing.return = returnFiber;
              // Return a reusable child fiber
              return existing;
            }
            break;
          }
        }
        // Unmatched delete nodes deleteRemainingChildren(returnFiber, child);
        break;
      } else {
        // Delete the node directly if the key is different deleteChild(returnFiber, child);
      }
      child = child.sibling;
    }

    // New Fiber node const created = createFiberFromElement(element, returnFiber.mode, lanes);
    created.ref = coerceRef(returnFiber, currentFirstChild, element);
    created.return = returnFiber;
    return created;
  }

if (isArray(newChild)) {
  return reconcileChildrenArray(
    returnFiber,
    currentFirstChild,
    newChild,
    lanes,
  );
}

if (getIteratorFn(newChild)) {
  return reconcileChildrenIterator(
    returnFiber,
    currentFirstChild,
    newChild,
    lanes,
  );
}

// Old node <li key="0"/>
<li key="1"/>
<li key="2"/>
// New node <li key="0"/>
<li key="1"/>
<li key="5"/>

// key="5" is different, jump out of traversal // The first round of traversal node <li key="0"/>
<li key="1"/>
// <li key="2"/> and <li key="5"/> are left in the second round of traversal and comparison.

// Old node <li key="0"/>
<li key="1"/>
<li key="2"/>
// New node <li key="0"/>
<li key="2"/>
<li key="1"/>

// The second round of traversal compares the two nodes <li key="2"/> and <li key="1"/>

  function reconcileChildrenArray(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    newChildren: Array<*>,
    lanes: Lanes,
  ): Fiber | null {
    // Fiber node returned by the function let resultingFirstChild: Fiber | null = null;
    let previousNewFiber: Fiber | null = null;

    // oldFiber is a linked list let oldFiber = currentFirstChild;
    // Used to determine whether the node is moved let lastPlacedIndex = 0;
    let newIdx = 0;
    let nextOldFiber = null;
    // In the first round of traversal, only nodes with the same key are traversed for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
      if (oldFiber.index > newIdx) {
        nextOldFiber = oldFiber;
        oldFiber = null;
      } else {
        // Each time the old fiber node is looped, it will point to the sibling element, which is the fiber node of the next loop nextOldFiber = oldFiber.sibling;
      }
      // If the key is the same, return the fiber node; if the key is different, return null
      // If the type is the same, reuse the node, otherwise return a new node const newFiber = updateSlot(
        returnFiber,
        oldFiber,
        newChildren[newIdx],
        lanes,
      );
      // newFiber is null, indicating that the key is different, and the loop will be exited if (newFiber === null) {
        if (oldFiber === null) {
          oldFiber = nextOldFiber;
        }
        break;
      }
      // If newFiber.alternate is null, it is a new node, indicating that a new fiber node is created with a different type if (oldFiber && newFiber.alternate === null) {
        // Need to delete the oldFiber tag deleteChild(returnFiber, oldFiber);
      }
      // Place the node and update lastPlacedIndex
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      // Form a new fiber node chain if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
      oldFiber = nextOldFiber;
    }

    /*
    After the first round of traversal, the number of new nodes is less than the number of old nodes. newChildren has been traversed and the remaining fiber nodes are deleted. The possible situation is as follows⬇️
    Before <li key="0"/>
    <li key="1"/>
    <li key="2"/>
    New <li key="0"/>
    <li key="1"/>
    <li key="2"/> will be deleted*/
    if (newIdx === newChildren.length) {
      deleteRemainingChildren(returnFiber, oldFiber);
      return resultingFirstChild;
    }

    /*
    After the first round of traversal, the number of new nodes is greater than the number of old nodes. OldFiber has been traversed. The possible situation is as follows⬇️
    Before <li key="0"/>
    <li key="1"/>
    New <li key="0"/>
    <li key="1"/>
    <li key="2"/>
    A new <li key="2"/> will be added. This section is the insertion logic of the new node*/
    if (oldFiber === null) {
      for (; newIdx < newChildren.length; newIdx++) {
        const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
        if (newFiber === null) {
          continue;
        }
        lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
        // Form a new fiber node chain if (previousNewFiber === null) {
          resultingFirstChild = newFiber;
        } else {
          previousNewFiber.sibling = newFiber;
        }
        previousNewFiber = newFiber;
      }
      return resultingFirstChild;
    }
      
    // ---------------------------------------------------------------------

    // Use the remaining oldFiber to create a key->fiber node Map, so that the corresponding old fiber node can be obtained by key const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
    
    // Second round of traversal, continue to traverse the remaining nodes, these nodes may need to be moved or deleted for (; newIdx < newChildren.length; newIdx++) {
      // Get the old node corresponding to the key from the map and return the updated new node const newFiber = updateFromMap(
        existingChildren,
        returnFiber,
        newIdx,
        newChildren[newIdx],
        lanes,
      );
      if (newFiber !== null) {
        // Reuse the new node and delete the old node from the map. The corresponding situation may be a change in position if (newFiber.alternate !== null) {
          // The reused nodes need to be removed from the map, because the remaining nodes in the map will be marked as Deletion existingChildren.delete(
            newFiber.key === null ? newIdx : newFiber.key,
          );
        }
        // Place the node and determine whether to move lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
        if (previousNewFiber === null) {
          resultingFirstChild = newFiber;
        } else {
          previousNewFiber.sibling = newFiber;
        }
        previousNewFiber = newFiber;
      }
    }

    // Delete the remaining useless nodes existingChildren.forEach(child => deleteChild(returnFiber, child));

    return resultingFirstChild;
  }

function placeChild(
  newFiber: Fiber,
  lastPlacedIndex: number,
  newIndex: number,
): number {
  newFiber.index = newIndex;
  const current = newFiber.alternate;
  if (current !== null) {
    const oldIndex = current.index;
    if (oldIndex < lastPlacedIndex) {
 			// Node movement newFiber.flags = Placement;
      return lastPlacedIndex;
    } else {
      // The node position has not changed return oldIndex;
    }
  } else {
    // Insert new node newFiber.flags = Placement;
    return lastPlacedIndex;
  }
}

// old abcd
// New acbd

// Old bcd
// New cbd

c => exists in the old node and can be reused. Its index in the old node is 2. 2 > lastPlacedIndex(0). No need to move. Assign lastPlacedIndex to 2.
b => exists in the old node and can be reused. Its index in the old node is 1, 1 < lastPlacedIndex(2). It needs to be moved and marked with Placement.
d => exists in the old node and can be reused. Its index in the old node is 3, 3 > lastPlacedIndex(2), so it does not need to be moved.