react diff算法完全解读

前言

diff算法在前端面试中也算是一个高频考题了，那怎么给面试官一个满分解答呢？难道还是简单的说个“深度优先，同层级比较”吗？这太短小精悍了……!

好了，下面开始进入正题

单节点diff

单节点diff就比较简单了，从同层级的老fiber节点中找出key值和type都相等的老节点，如果该老fiber节点存在，则复用他，然后删除剩余的节点，否则重新生成一个新的fiber节点（这也就意味着以这个节点为根的子树需要重新生成）。
下面我们来看看单节点diff的核心源码

function reconcileSingleElement(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  element: ReactElement,
  lanes: Lanes
): Fiber {
  const key = element.key;
  let child = currentFirstChild;
  // 遍历同层级的老fiber节点
  while (child !== null) {
    if (child.key === key) {
      const elementType = element.type;
      // 从老fiber节点中找出key和type都相同的节点，如果找到则将该节点复用，并删除多余的节点，退出循环
      if (child.elementType === elementType) {
        deleteRemainingChildren(returnFiber, child.sibling);
        const existing = useFiber(child, element.props);
        existing.ref = coerceRef(returnFiber, child, element);
        existing.return = returnFiber;
        return existing;
      }
      deleteRemainingChildren(returnFiber, child);
      break;
    } else {
      // 如果该fiber节点没匹配上，则删除
      deleteChild(returnFiber, child);
    }
    child = child.sibling;
  }

  // 能走到这里就意味着无法从老fiber中匹配到key和type都相同的节点，无法复用，需要重新生成
  const created = createFiberFromElement(element, returnFiber.mode, lanes);
  created.return = returnFiber;
  return created;
}

复制代码

多节点diff

重点来了，注意了啊，多节点才是精髓

目前页面上有3个li，内容和key分别为1、2、3（fiber树如下图所示）
ReactChildren (1).png

现在我要让页面变成3个li，内容和key分别是1、3、2，其所对应的ReactElement结构为

[
    {$$typeof: REACT_ELEMENT_TYPE, type: 'li', props: {children: 1}, key: 1, ...},
    {$$typeof: REACT_ELEMENT_TYPE, type: 'li', props: {children: 3}, key: 3, ...},
    {$$typeof: REACT_ELEMENT_TYPE, type: 'li', props: {children: 2}, key: 2, ...},
]
复制代码

那么react怎么做呢？

首先会定义一个lastPlacedIndex用来作为基准位置来判断旧节点是否需要移动，初始为0
第一轮遍历新的children即ReactElement，即1、3、2，遍历的同时，旧fiber也跟着指向下一个兄弟节点，如果key和type都相同，则代表该fiber节点可以复用，否则退出第一轮循环。看到这，该oldFiber是可以复用，将该oldFiber的index值与lastPlaceIndex比较，如果oldIndex<lastPlaceIndex，则表示新生成的fiber节点需要移动，打上Placement的标记，lastPlaceIndex保持不变，否则lastPlaceIndex=oldIndex
第一轮循环结束后，有三种情况：1.newChildren都遍历完（最理想的情况，只需要删除剩余的oldFibers）；2.oldFibers遍历完了，但是newChildren还没遍历完（这种情况也没那么复杂，只需要为剩余的newChildren创建fiber节点即可）；3.newChildren和oldFibers都没遍历完（最复杂的情况了，需要开启第二轮循环）
将剩余的oldFibers存入map中，oldFiber有key的以key作为map的key值，没key的以index作为map的key值，oldFiber作为value值
第二轮循环开启，遍历未遍历完的newChildren：从map中寻找以newChild.key||newIndex为key的oldFiber，如果该oldFiber存在，则使用它（type相同则复用，不相同则生成）创建newFiber，然后将该oldFiber从map中删除，然后将该如果该newFiber是复用来的，他就存在alternate，newFiber.alternate == oldFiber，可以跟lastPlaceIndex进行比较如果oldIndex<lastPlaceIndex，则表示新生成的fiber节点需要重新插入，打上Placement的标记，lastPlaceIndex保持不变，否则lastPlaceIndex=oldIndex；如果newFiber是重新生成的，则newFiber.alternate == null，直接打上Placement标签即可，lastPlaceIndex保持不变。
第二轮循环结束后，删除map中剩余的oldFiber

复杂的流程如下图所示：

幻灯片1.png

幻灯片2.png

幻灯片3.png

幻灯片4.png

幻灯片5.png

幻灯片6.png

幻灯片7.png

下面来看下react diff代码片段的实现

function reconcileChildrenArray(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChildren: Array<*>,
  lanes: Lanes
): Fiber | null {

  let resultingFirstChild: Fiber | null = null;
  let previousNewFiber: Fiber | null = null;

  let oldFiber = currentFirstChild;
  let lastPlacedIndex = 0;
  let newIdx = 0;
  let nextOldFiber = null;
  // 第一轮遍历
  for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
    // ...
    nextOldFiber = oldFiber.sibling;
    // 如果type和key相同则复用该fiber节点返回一个newFiber，否则返回null，然后跳出第一轮循环
    const newFiber = updateSlot(
      returnFiber,
      oldFiber,
      newChildren[newIdx],
      lanes
    );
    if (newFiber === null) {
      // ...
      break;
    }
    if (oldFiber && newFiber.alternate === null) {
      // 兜底操作，如果该newFiber不是复用来的，就将oldFiber标记为删除
      deleteChild(returnFiber, oldFiber);
    }
    // 标记该newFiber是否需要重新插入
    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
    if (previousNewFiber === null) {
      resultingFirstChild = newFiber;
    } else {
      previousNewFiber.sibling = newFiber;
    }
    previousNewFiber = newFiber;
    oldFiber = nextOldFiber;
  }

  // 第一轮循环结束，newChildren遍历完成，删除多余的oldFiber
  if (newIdx === newChildren.length) {
    // We've reached the end of the new children. We can delete the rest.
    deleteRemainingChildren(returnFiber, oldFiber);
    return resultingFirstChild;
  }

  if (oldFiber === null) {
    // 老fiber被遍历完了，但是newChildren还未遍历完，则需要生成fiber并标记为需要插入
    for (; newIdx < newChildren.length; newIdx++) {
      const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
      if (newFiber === null) {
        continue;
      }
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
    }
    return resultingFirstChild;
  }

  // 将剩余的oldFiber存入map中，key=oldFiber.key||oldFiber.index
  const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

  // 遍历剩余的newChildren
  for (; newIdx < newChildren.length; newIdx++) {
    // 从map中查询是否有oldFiber可以复用，根据newChild.key||newIndex来查询，有则复用，没有则重新生成
    const newFiber = updateFromMap(
      existingChildren,
      returnFiber,
      newIdx,
      newChildren[newIdx],
      lanes
    );
    if (newFiber !== null) {
      // 走到这里说明newFiber是生成而来的
      if (newFiber.alternate !== null) {
        // 从map中移除已经被复用的oldFiber
        existingChildren.delete(newFiber.key === null ? newIdx : newFiber.key);
      }
      // 判断该节点是否需要移动
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
    }
  }

  // 删除map中剩余的oldFiber
  existingChildren.forEach((child) => deleteChild(returnFiber, child));

  return resultingFirstChild;
}

复制代码