深入理解React Diff算法：从O(n³)到O(n)的性能优化之道

Level 1:        A       ←→      A'
              /   \           /   \
Level 2:     B     C   ←→    B'    C'
            / \             / \
Level 3:   D   E           D'  E'

// 场景1：同类组件
<MyComponent data={oldData} />  →  <MyComponent data={newData} />
// React会更新props，继续Diff子节点

// 场景2：不同类组件
<ComponentA />  →  <ComponentB />
// React会直接卸载ComponentA，挂载ComponentB

// 更新前：多个子节点
<div>
  <p key="a">1</p>
  <p key="b">2</p>
  <p key="c">3</p>
</div>

// 更新后：单个子节点
<div>
  <p key="a">1</p>
</div>

// React源码简化版
function reconcileSingleElement(
  returnFiber,
  currentFirstChild,
  element
) {
  const key = element.key;
  let child = currentFirstChild;
  
  // 遍历所有旧的子节点
  while (child !== null) {
    // 步骤一：比较key
    if (child.key === key) {
      // 步骤二：比较type
      if (child.elementType === element.type) {
        // key和type都相同，复用节点
        deleteRemainingChildren(returnFiber, child.sibling);
        const existing = useFiber(child, element.props);
        return existing;
      } else {
        // key相同但type不同，删除所有旧节点
        deleteRemainingChildren(returnFiber, child);
        break;
      }
    } else {
      // key不同，删除该节点，继续遍历兄弟节点
      deleteChild(returnFiber, child);
    }
    child = child.sibling;
  }
  
  // 创建新节点
  const created = createFiberFromElement(element);
  return created;
}

// 场景1：key相同，type相同 → 复用
<div key="a">old</div>  →  <div key="a">new</div>
// 结果：复用div节点，更新文本内容

// 场景2：key相同，type不同 → 不复用
<div key="a">content</div>  →  <p key="a">content</p>
// 结果：删除div，创建新的p

// 场景3：key不同 → 不复用
<div key="a">content</div>  →  <div key="b">content</div>
// 结果：删除旧div，创建新div

// 更新前
<ul>
  <li key="a">A</li>
  <li key="b">B</li>
  <li key="c">C</li>
</ul>

// 更新后
<ul>
  <li key="c">C</li>
  <li key="a">A</li>
  <li key="d">D</li>
</ul>

// Fiber节点的链表结构
{
  child: firstChildFiber,    // 指向第一个子节点
  sibling: nextSiblingFiber, // 指向下一个兄弟节点
  // 注意：没有 prevSibling 反向指针！
}

// react-reconciler/src/ReactChildFiber.js - reconcileChildrenArray
for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
  // 处理稀疏数组的情况：
  // 由于子fiber通过sibling链表连接，index用于记录其在数组中的实际位置
  // 理想情况下，newIdx和oldFiber.index应该同步前进
  // 但考虑到稀疏数组（如 [1, , 3]）的情况，index可能不等于其在链表中的位置
  // 如果oldFiber.index > newIdx，说明当前newChildren[newIdx]对应的是空值
  // 此时让oldFiber暂时为null，与这个空的新子节点比较
  // 注意：新子节点本身也可能是null/undefined
  if (oldFiber.index > newIdx) {
    nextOldFiber = oldFiber;
    oldFiber = null;
  } else {
    nextOldFiber = oldFiber.sibling;
  }
  
  // 现在比较新旧节点，期望它们能够匹配
  // updateSlot()内部逻辑：
  // - 如果新子节点是空值（null/undefined）→ 返回null
  // - 如果新子节点的key与旧节点的key不匹配 → 返回null
  // - 如果key匹配，则创建/复用fiber并返回
  const newFiber = updateSlot(
    returnFiber,
    oldFiber,
    newChildren[newIdx],
    lanes
  );
  
  // 如果newFiber为null，说明当前位置的新旧节点无法配对
  // 此时需要通过第二轮遍历来：
  // 1. 从Map中查找该新节点在旧列表中的原始位置（复用）
  // 2. 或者创建一个全新的fiber
  // 所以这里break跳出第一轮遍历
  if (newFiber === null) {
    if (oldFiber === null) {
      oldFiber = nextOldFiber;
    }
    break;
  }
  
  // key匹配但type不同：newFiber.alternate为null，需要删除旧节点
  if (shouldTrackSideEffects) {
    if (oldFiber && newFiber.alternate === null) {
      deleteChild(returnFiber, oldFiber);
    }
  }
  
  // 我们成功获取了一个新fiber！
  // 现在需要标记这个fiber，告诉React在commit阶段把其DOM节点移动到新位置
  // lastPlacedIndex非常有趣，我们稍后会详细讲解
  lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
  
  // 我们需要把这些fiber串联成链表
  // previousNewFiber允许我们通过sibling指针连接各个fiber
  if (previousNewFiber === null) {
    resultingFirstChild = newFiber;
  } else {
    previousNewFiber.sibling = newFiber;
  }
  previousNewFiber = newFiber;
  oldFiber = nextOldFiber;
}

// 由于我们还有新子节点需要检查
// 让我们看看能否在现有的fiber中找到相同的key
// 如果找到了，就可以复用它们进行后续reconcile
// 把所有剩余的旧子节点添加到key Map中以便快速查找
// 这里实际上是把链表转换回类似数组的结构（Map）
// 继续扫描新节点，并使用Map将"已删除"的节点恢复为"移动"操作
const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

// 遍历剩余的新节点
for (; newIdx < newChildren.length; newIdx++) {
  // 从Map中查找可复用的fiber
  const newFiber = updateFromMap(
    existingChildren,
    returnFiber,
    newIdx,
    newChildren[newIdx],
    lanes
  );
  
  if (newFiber !== null) {
    if (shouldTrackSideEffects) {
      if (newFiber.alternate !== null) {
        // 复用了旧节点，从Map中删除
        existingChildren.delete(
          newFiber.key === null ? newIdx : newFiber.key
        );
      }
    }
    // 判断是否需要移动
    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
    // 构建链表...
  }
}

// 删除Map中剩余的旧节点（它们在新列表中不存在）
if (shouldTrackSideEffects) {
  existingChildren.forEach(child => deleteChild(returnFiber, child));
}

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) {
      // 旧位置在lastPlacedIndex左边，说明需要向右移动
      newFiber.flags |= Placement;
      return lastPlacedIndex; // 不更新lastPlacedIndex
    } else {
      // 旧位置在lastPlacedIndex右边或相等，不需要移动
      return oldIndex; // 更新lastPlacedIndex为当前旧位置
    }
  } else {
    // 新创建的节点，需要插入
    newFiber.flags |= Placement;
    return lastPlacedIndex;
  }
}

旧顺序: [1] [2] [3] [4] [5] [6]
新顺序: [1] [6] [2] [5] [4] [3]

function insertOrAppendPlacementNode(
  node: Fiber,
  before: ?Instance,
  parent: Instance
): void {
  const { tag } = node;
  const isHost = tag === HostComponent || tag === HostText;
  
  if (isHost) {
    const stateNode = node.stateNode;
    if (before) {
      insertBefore(parent, stateNode, before);
    } else {
      appendChild(parent, stateNode);
    }
  } else {
    // 处理非Host节点（如Fragment）的子节点
    const child = node.child;
    if (child !== null) {
      insertOrAppendPlacementNode(child, before, parent);
      let sibling = child.sibling;
      while (sibling !== null) {
        insertOrAppendPlacementNode(sibling, before, parent);
        sibling = sibling.sibling;
      }
    }
  }
}