react diff算法源码解析

目录

• 单节点Diff
  • reconcileSingleElement
• 多节点Diff
  • reconcileChildrenArray
  • 如何判断节点移动了？
• 总结

React中Diff算法又称为调和算法，对应函数名为reconcileChildren，它的主要作用是标记更新过程中那些元素发生了变化，这些变化包括新增、移动、删除。过程发生在beginWork阶段，只有非初次渲染才会Diff。

以前看过一些文章将Diff算法表述为两颗Fiber树的比较，这是不正确的，实际的Diff过程是一组现有的Fiber节点和新的由JSX生成的ReactElement的比较，然后生成新的Fiber节点的过程，这个过程中也会尝试复用现有Fiber节点。

节点Diff又分为两种：

1. 单节点Diff —— Element、Portal、string、number。
2. 多节点Diff —— Array、Iterator。

以下React版本为17.0.1，代码文件为ReactChildFiber.old.js。

单节点Diff

单节点Diff比较简单，只有key相同并且type相同的情况才会尝试复用节点，否则会返回新的节点。

单节点大部分情况下我们都不会去赋值key，所以它们默认为null，也是相同的。

reconcileSingleElement

// 单节点比较
function reconcileSingleElement(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  element: ReactElement,
  lanes: Lanes,
): Fiber {
  // 当前新的reactElement的key
  const key = element.key;
  // 当前的child fiber节点
  let child = currentFirstChild;
  while (child !== null) {
    // key相同的情况才diff
    if (child.key === key) {
      switch (child.tag) {
        // ...
        default: {
          // 当前fiber和reactElement的type相同时
          if (child.elementType === element.type) {
            // 删除同级的其他节点
            deleteRemainingChildren(returnFiber, child.sibling);
            // 复用当前child fiber
            const existing = useFiber(child, element.props);
            existing.ref = coerceRef(returnFiber, child, element);
            existing.return = returnFiber;
            // 返回可复用的child fiber
            return existing;
          }
          break;
        }
      }
      // 不匹配删除节点
      deleteRemainingChildren(returnFiber, child);
      break;
    } else {
      // key不同直接删除节点
      deleteChild(returnFiber, child);
    }
    child = child.sibling;
  }

  // 新的Fiber节点
  const created = createFiberFromElement(element, returnFiber.mode, lanes);
  created.ref = coerceRef(returnFiber, currentFirstChild, element);
  created.return = returnFiber;
  return created;
}

多节点Diff

源码中将多节点分为了数组节点和可迭代节点。

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

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

对应的Diff函数分别是reconcileChildrenArray和reconcileChildrenIterator。它们的核心Diff逻辑是相同的，所以只分析数组节点的Diff —— reconcileChildrenArray函数。

这一段的代码比较长，但逻辑很清晰，从分割线分为两轮遍历。

• 第一轮遍历的是顺序相同且key也相同的节点，这些节点需要做更新操作。
• 第二轮遍历的是顺序不同，可能key也不同的节点，这些节点需要做新增、移动或删除操作。

第一轮遍历只针对key和顺序都相同的情况，这些key对应的节点位置没有发生改变，只需要做更新操作，一旦遍历遇到key不同的情况就需要跳出循环。

// 旧节点
<li key="0"/>
<li key="1"/>
<li key="2"/>
// 新节点
<li key="0"/>
<li key="1"/>
<li key="5"/>

// key="5"不同，跳出遍历
// 第一轮遍历的节点
<li key="0"/>
<li key="1"/>
// <li key="2"/>和<li key="5"/>留在第二轮遍历比较。

在第一轮遍历完后也分为两种情况。

1. 新节点数量少于旧节点数量，这时候需要把多余的旧节点标记为删除。
2. 新节点数量大于旧节点数量，这时候需要把多余的新节点标记为新增。

第二轮遍历针对key不同或顺序不同的情况，可能情况如下：

// 旧节点
<li key="0"/>
<li key="1"/>
<li key="2"/>
// 新节点
<li key="0"/>
<li key="2"/>
<li key="1"/>

// 第二轮遍历对比<li key="2"/>、<li key="1"/>这两个节点

第二轮的遍历会稍微复杂一点，后文在细讲。

详细的代码如下。

reconcileChildrenArray

function reconcileChildrenArray(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChildren: Array<*>,
  lanes: Lanes,
): Fiber | null {
  // 函数返回的Fiber节点
  let resultingFirstChild: Fiber | null = null;
  let previousNewFiber: Fiber | null = null;

  // oldFiber为链表
  let oldFiber = currentFirstChild;
  // 用来判断节点是否移动
  let lastPlacedIndex = 0;
  let newIdx = 0;
  let nextOldFiber = null;
  // 第一轮遍历，只遍历key相同的节点
  for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
    if (oldFiber.index > newIdx) {
      nextOldFiber = oldFiber;
      oldFiber = null;
    } else {
      // 每次循环旧的fiber节点都会指向兄弟元素也就是下次循环的fiber节点
      nextOldFiber = oldFiber.sibling;
    }
    // key相同返回fiber节点，key不同返回null
    // 如果type相同复用节点，不同返回新节点
    const newFiber = updateSlot(
      returnFiber,
      oldFiber,
      newChildren[newIdx],
      lanes,
    );
    // newFiber为null表示key不同，跳出循环
    if (newFiber === null) {
      if (oldFiber === null) {
        oldFiber = nextOldFiber;
      }
      break;
    }
    // newFiber.alternate为null就是新节点，说明type不同创建了新fiber节点
    if (oldFiber && newFiber.alternate === null) {
      // 需要把oldFiber标记删除
      deleteChild(returnFiber, oldFiber);
    }
    // 放置节点,更新lastPlacedIndex
    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
    // 组成新fiber节点链
    if (previousNewFiber === null) {
      resultingFirstChild = newFiber;
    } else {
      previousNewFiber.sibling = newFiber;
    }
    previousNewFiber = newFiber;
    oldFiber = nextOldFiber;
  }

  /*
  第一轮遍历完后新节点数量少于旧节点数量
  newChildren已经遍历完，删除掉剩下的fiber节点，可能情况如下 ⬇️
  以前
  <li key="0"/>
  <li key="1"/>
  <li key="2"/>
  新的
  <li key="0"/>
  <li key="1"/>
  就会把<li key="2"/>删除
   */
  if (newIdx === newChildren.length) {
    deleteRemainingChildren(returnFiber, oldFiber);
    return resultingFirstChild;
  }

  /*
  第一轮遍历完新节点数量大于旧节点数量
  oldFiber已经遍历完，可能情况如下 ⬇️
  以前
  <li key="0"/>
  <li key="1"/>
  新的
  <li key="0"/>
  <li key="1"/>
  <li key="2"/>
  就会添加新的<li key="2"/>，这一段是新节点的插入逻辑
   */
  if (oldFiber === null) {
    for (; newIdx < newChildren.length; newIdx++) {
      const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
      if (newFiber === null) {
        continue;
      }
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      // 组成新fiber节点链
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
    }
    return resultingFirstChild;
  }

  // ---------------------------------------------------------------------

  // 用剩余的oldFiber创建一个key->fiber节点的Map，方便用key来获取对应的旧fiber节点
  const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

  // 第二轮遍历，继续遍历剩余的节点，这些节点可能是需要移动或者删除的
  for (; newIdx < newChildren.length; newIdx++) {
    // 从map中获取对应对应key的旧节点，返回更新后的新节点
    const newFiber = updateFromMap(
      existingChildren,
      returnFiber,
      newIdx,
      newChildren[newIdx],
      lanes,
    );
    if (newFiber !== null) {
      // 复用的新节点，从map里删除老的节点，对应的情况可能是位置的改变
      if (newFiber.alternate !== null) {
        // 复用的节点要移除map，因为map里剩余的节点都会被标记Deletion删除
        existingChildren.delete(
          newFiber.key === null ? newIdx : newFiber.key,
        );
      }
      // 放置节点同时节点判断是否移动
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
    }
  }

  // 删除剩下的无用节点
  existingChildren.forEach(child => deleteChild(returnFiber, child));

  return resultingFirstChild;
}

第一轮遍历比较好理解，这里再细分析一下第二轮遍历，因为第二轮会出现复用是否需要移动的问题。

第二轮遍历首先遍历剩余的oldFiber，组成一个key -> 旧fiber节点的Map，这用可以通过key来快速的获取旧节点。

接下来的遍历依然是使用的新节点为遍历对象，每次遍历使用新节点的key从Map中取出旧节点来对比是否能复用，对应的函数为updateFromMap。

如果节点存在alternate属性，则是复用的节点，这时候需要将它从existingChildren里移除，后续会把第二轮遍历完后依然存在在existingChildren里的节点标记为删除。

如何判断节点移动了？

这里存在一个变量lastPlacedIndex用来判断节点是否移动，每次将节点添加到新的Fiber链表中，都会更新这个值。

当复用的节点oldIndex小于lastPlacedIndex时，则为移动，如果不需要移动，则会将lastPlacedIndex更新为较大的oldIndex，下一个节点会以新值判断，代码如下：

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) {
            // 节点移动
      newFiber.flags = Placement;
      return lastPlacedIndex;
    } else {
      // 节点位置无变化
      return oldIndex;
    }
  } else {
    // 插入的新节点
    newFiber.flags = Placement;
    return lastPlacedIndex;
  }
}

举个例子：

// 旧
abcd
// 新
acbd

abcd均为key值。

第一轮遍历后剩下的需要对比节点:

// 旧
bcd
// 新
cbd

a节点在第一轮已经复用，并且调用过placeChild，这时lastPlacedIndex值为0。

进入第二轮遍历，依然是以新节点为遍历对象。

c => 在旧节点中存在，可复用，它的index在旧节点中为2，2 > lastPlacedIndex(0)，不需要移动,将lastPlacedIndex赋值为2。
b => 在旧节点中存在，可复用，它的index在旧节点中为1，1 < lastPlacedIndex(2)，需要移动，标记Placement。
d => 在旧节点中存在，可复用，它的index在旧节点中为3，3 > lastPlacedIndex(2)，不需要移动。

由这个例子可以看出，React中将右侧不需要移动的节点作为参照，将需要移动的节点都是统一从左向右移动的。

在后续Layout阶段会将这里标记了Placement的节点做insertBefore操作。

总结

React中的Diff算法核心代码不算很长，但是却引入key巧妙的将复杂度由O(n3 )变为了O(n)。

码农内卷太严重，所以不得不学习源码了。

以上就是react diff算法源码解析的详细内容，更多关于react diff算法的资料请关注服务器之家其它相关文章！

原文链接：https://juejin.cn/post/6949092569275957256