从源码的角度理解 React Diff

在react中，更新UI必须生成新的JSX对象（称之为visual DOM），而新的JSX对象和老的visual DOM之间对比以最小的操作次数来获取差异节点（也称之为副作用），从而高效的更新UI。

用现在最优的算法解决也需要时间复杂度为O(n^3)来解决，这对于web页面这么多的节点而言，采用这种算法代价太高了，可以说是灾难。

不过，react在两个假设的基础上提出了一套时间复杂度为O(n)的算法，而这种算法在操作DOM的场景下都成立。

  1. 不同类型的元素会产生不同的树，比如之前节点类型是p，之后又变成了div，那么这两个节点是不同的两棵树。
  2. 节点的属性key值可以限制节点能否复用，如果前后前两个节点的key值不同，则两个节点也是不同的两个树。

最重要的一点，执行这两个限制条件的前提是必须是同级对比，如果节点跨层级了，那么也不会去复用，而是去新建一个节点。这样才能保证该算法的时间复杂度为O(n),n为节点的个数。

react中，有两种类型的diff算法，单节点diff和多节点diff。

从源码看，diff算法是在render阶段的beginWork中。

beginWork主要有两个过程（mount和update）：

  • update（更新）阶段主要是diff算法的过程。
  • mount(挂载)阶段主要是创建Fiber树的过程。

下面是diff算法的入口：

// react/packages/react-reconciler/src/ReactChildFiber.old.js
reconcileChildFibers(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    newChild: any,
    lanes: Lanes,
  ): Fiber | null {
    const isObject = typeof newChild === 'object' && newChild !== null;
    if (isObject) {
      switch (newChild.$$typeof) {
        case REACT_ELEMENT_TYPE:
          return placeSingleChild(
            // 单节点 diff
            reconcileSingleElement(
              returnFiber,
              currentFirstChild,
              newChild,
              lanes,
            ),
          );
      }
    }
    if (typeof newChild === 'string' || typeof newChild === 'number') {
      // reconcileSingleTextNode
    }
    if (isArray(newChild)) {
      // reconcileChildrenArray 多节点diff
    }
    //... 其他处理
    // 没有找到上述类型，则删除节点
    return deleteRemainingChildren(returnFiber, currentFirstChild);
  }
  return reconcileChildFibers;
}

单节点Diff

单节点Diff源码这里

单节点更新的类型：

  1. 单节点更新之后为单节点
  2. 多节点更新之后为单节点

首先看一下入口函数：

// react/packages/react-reconciler/src/ReactChildFiber.old.js
/**
 * returnFiber 指向当前构建的workInProgress Fiber节点 的父级节点
 * currentFirstChild 当前页面展示的 current Fiber，也是需要更新的节点
 * element 当前需要更新的最新节点 也就是JSX对象
 */
function reconcileSingleElement(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  element: ReactElement,
  lanes: Lanes,
): Fiber {
  const key = element.key;
  let child = currentFirstChild;
  // update 阶段 child 不为 null
  while (child !== null) {
    if (child.key === key) {
      switch (child.tag) {
        case Fragment: {
          // 处理 Fragment
        }
        case Block:
          // 处理 Block
        default: {
          if (
            child.elementType === element.type
          ) {
            // 为当前节点的所有兄弟节点打上Deletion的EffectTag，因为单节点一旦复用，其他兄弟节点都会被标记删除
            // 同时构建EffectList链表
            deleteRemainingChildren(returnFiber, child.sibling);
            const existing = useFiber(child, element.props);
            existing.ref = coerceRef(returnFiber, child, element);
            existing.return = returnFiber;
            return existing;
          }
          break;
        }
      }
      // Didn't match.
      deleteRemainingChildren(returnFiber, child);
      break;
    } else {
      // 给需要删除的节点打上Deletion的EffectTag，并且构建effectList链表
      deleteChild(returnFiber, child);
    }
    // 存在 多节点更新之后变为单节点
    child = child.sibling;
  }


  if (element.type === REACT_FRAGMENT_TYPE) {
    // 处理 Fragment
  } else {
    // 创建新的Fiber节点 根据JSX type
    const created = createFiberFromElement(element, returnFiber.mode, lanes);
    created.ref = coerceRef(returnFiber, currentFirstChild, element);
    created.return = returnFiber;
    return created;
  }
}

首先，有一个while循环，这里有两次含义：

  1. 首次渲染的时候，因为currentFiber不存在，因此currentFirstChild == null，直接创建Fiber节点。
  2. 当更新的时候，currentFiber已经存在，如果是多节点更新为单节点，此时会走while循环。

接着，如果是更新的场景，则会判断是否能够复用节点。这里是单节点diff的核心。

最后，将当前的Fiber节点（不管是复用的还是新创建的）返回作为workInProgress.child的值。

下面为单节点diff的流程图

diff-single-loop

其中，最核心还是oldFiber和element的diff对比过程，

从diff单节点的两个场景分别看下如果进行diff对比，以及最终生成的effectList。

单节点到单节点对比

如下代码，

<!-- 更新前 -->
<div>
  <span key='a'>0</span>
</div>


<!-- 更新后 -->
<div>
  <span key='a'>1</span>
</div>

更新前后，元素的key和type都没有变化，因此在diff过程中可以复用oldFiber作为当前构建的workInProgress。

因为前后都是单节点，所以不存在去删除其兄弟节点（为其兄弟节点打上Deletion的effectTag），所以diff过程是没有生成effectList的，但是节点更新了，肯定会生成effectList的，这个过程是在render阶段中completeWork中，

completeWork也有两个过程（mount和update）：

  • update（更新）阶段主要是计算newProps和oldProps的差异，如果存在，则为当前Fiber打上Update的effectTag。
  • mount(挂载)阶段主要是创建Fiber节点对应的DOM节点的过程。

所以，更新前后的span标签的children更新的，所以span标签的Fiber节点会有Update的effectTag。

有了effectTag，在completeUnitOfWork阶段的最后会生成effectList

这里可以看到在completeWork阶段处理effectList链表的源码

多节点到单节点对比

如下代码：

<!-- 更新前 -->
<div>
  <span key='a'>0</span>
  <span key='b'>1</span>
  <span key='c'>2</span>
  <span key='d'>3</span>
</div>


<!-- 更新后 -->
<div>
  <span key='c'>4</span>
</div>

因为oldFiber div节点是多节点，遍历其每一个节点与更新后的JSX对象对比，如上图，如果没有复用的节点，就执行deleteRemainingChildren(returnFiber, child);，给当前oldFiber节点打上Deletion的effectTag，同时生成effectList链表。

如果碰到可以复用的节点，执行deleteRemainingChildren(returnFiber, child.sibling);，注意，这里的参数是child.sibling，因为此时已经匹配到了节点，需要删除当前节点的所有兄弟节点，并且将要删除的节点添加到effectList链表中。

这样，多节点到单节点的diff操作结束，返回复用的节点作为父节点的child。

之后，同样进入render阶段中的completeWork，对复用的节点进行oldProps和newProps的对比，如果有差异，则给当前节点打上Update的effectTag，并且将该节点添加到effectList链表中。

至此，多节点到单节点的整个协调过程全部结束，生成的effectList链表被保存在父节点的firstEffect属性中。

下图，展示了最终生成的effectList链表。黄色的线是effectList的走向。

多节点Diff

从源码这里角度来看，多节点Diff算法会有两轮循环。

多节点主要有以下几种方式需要更新：

  1. 节点更新
  2. 节点增加或者减少
  3. 节点位置变化

由于Web UI的更新主要以更新为主，所以第一轮循环主要解决节点的更新。

首先看下源码入口:

// 多节点 Diff 入口
function reconcileChildrenArray(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChildren: Array<*>,
  lanes: Lanes
): Fiber | null {
  // * 最终返回的fiber节点 - 也就是带有sibling的子链表
  let resultingFirstChild: Fiber | null = null;
  // * 中间变量 用来保存每一次新生成的newFiber
  let previousNewFiber: Fiber | null = null;


  // * 用来跟newChildren对比的currentFiber
  let oldFiber = currentFirstChild;
  // * 中间变量 用来保存oldFiber 链表的当前节点
  let nextOldFiber = null;


  // * 用来记录Fiber节点对应的DOM节点的位置
  let lastPlacedIndex = 0;


  // * 遍历更新元素数组的索引
  let newIdx = 0;


  // TODO ...
  return resultingFirstChild;
}

首先可以看到，多节点更新逻辑的输入参数为currentFirstChild、newChildren和returnFiber，以及初始化定义的参数，在后面会具体说明。

returnFiber就是当前需要对比节点的父节点对应的current Fiber树。

currentFirstChild为当前页面呈现的current fiber树的第一个子Fiber节点。

newChildren为页面更新之后的包含新JSX对象的数组。

而返回的resultingFirstChild是WorkInProgress Fiber节点，也就是diff操作之后最新的Fiber，可以看到上图右上侧对应的Fiber 双缓存树上的节点。

第一轮循环

first-loop

从第一轮循环图可以看到，如果oldFiber老节点和newChildren[newIdx]新节点的type和key相同，因此，在生成新的 Fiber 节点的时候，会直接复用oldFiber节点，而这种场景节点数量、顺序都没有变化，所以在第一轮循环中，newChildren和oldFiber都遍历完了。

// 第一遍轮换
for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
  if (oldFiber.index > newIdx) {
    nextOldFiber = oldFiber;
    oldFiber = null;
  } else {
    nextOldFiber = oldFiber.sibling;
  }
  const newFiber = updateSlot(
    returnFiber,
    oldFiber,
    newChildren[newIdx],
    lanes
  );
  // key值不同，不能复用，直接跳出循环，进入第二轮循环
  if (newFiber === null) {
    if (oldFiber === null) {
      oldFiber = nextOldFiber;
    }
    break;
  }
  // shouldTrackSideEffects 更新节点为true
  if (shouldTrackSideEffects) {
    // 新创建的Fiber节点 alternate 为 null
    if (oldFiber && newFiber.alternate === null) {
      deleteChild(returnFiber, oldFiber);
    }
  }


  lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);


  if (previousNewFiber === null) {
    resultingFirstChild = newFiber;
  } else {
    previousNewFiber.sibling = newFiber;
  }
  previousNewFiber = newFiber;
  oldFiber = nextOldFiber;
}
// newChildren 遍历结束 直接跳出第一轮循环
if (newIdx === newChildren.length) {
  // We've reached the end of the new children. We can delete the rest.
  deleteRemainingChildren(returnFiber, oldFiber);
  return resultingFirstChild;
}

第一轮遍历主要判断Fiber节点是否能复用，而复用的逻辑主要在updateSlot函数源码这里中。

updateSlot会根据oldFiber和newChildren[newIdx]的key、elementType对比，如果key不同，直接返回null空节点，此时newFiber=null，则跳出第一轮循环。

否则根据elementType判断，相同则复用oldFiber，不同则创建新的Fiber的节点，如果是新增的节点，则会在oldFiber节点打上Delete的effectTag，标记需要删除，同时处理current Fiber树的EffectList。

否则在新Fiber节点上打上Placement的effectTag，标记需要更新的节点。

最后更新resultingFirstChild链表，进行下一次循环，直到newChildren遍历结束，然后跳出循环。

第二轮循环

从第一轮的图看到，只有当oldFiber和newChildren都遍历结束之后，第一轮才会结束。

那么进入第二轮循环的条件是：

  1. oldFiber没有遍历完，newChildren没有遍历完
  2. oldFiber没有遍历，newChildren遍历结束
  3. oldFiber遍历完，newChildren没有遍历完

进入第二轮主要的场景有:

  • 节点增加 - 符合上述场景3
  • 节点减少 - 符合上述场景2
  • 节点移动 - 符合上述场景1

从上图中可以看到，当符合场景3的时候，会为每一个新增的节点闯将对应的Fiber节点，然后打上Placement的effectTag，然后结束Diff 算法。

// 符合场景3 的源码
if (oldFiber === null) {
  for (; newIdx < newChildren.length; newIdx++) {
    // 创建Fiber
    const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
    if (newFiber === null) {
      continue;
    }
    // 为Fiber添加Placement的Tag
    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
    if (previousNewFiber === null) {
      resultingFirstChild = newFiber;
    } else {
      previousNewFiber.sibling = newFiber;
    }
    previousNewFiber = newFiber;
  }
  return resultingFirstChild;
}

当符合场景1和场景2的时候，此时oldFiber和newChildren都没有遍历完，为了降低算法的时间复杂度，采用了空间换时间的方式。

将剩余的oldFiber加入了哈希表中，然后只遍历newChildren，根据newChildren[newIdx]的key来判定是否可以复用节点，之后的流程就跟第一轮的复用逻辑一致了。最后，返回workInProgress的fiber子树，作为其return Fiber的child子属性。

// 符合场景1、2的源码


// oldFiber添加Map
const existingChildren = mapRemainingChildren(returnFiber, oldFiber);


for (; newIdx < newChildren.length; newIdx++) {
  // 复用逻辑
  const newFiber = updateFromMap(
    existingChildren,
    returnFiber,
    newIdx,
    newChildren[newIdx],
    lanes,
  );
  if (newFiber !== null) {
    if (shouldTrackSideEffects) {
      if (newFiber.alternate !== null) {
        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节点的话，直接当上Deletion的EffectTag
if (shouldTrackSideEffects) {
  existingChildren.forEach(child => deleteChild(returnFiber, child));
}
return resultingFirstChild;

至此，多节点的Diff算法的大致过程就结束了，下面针对每种不同的场景看下对应的双缓存的Fiber树和其产生的effectList。

节点更新

节点更新有节点属性更新和节点类型更新

节点属性更新

如下图，更新之前和之后，元素的类型type和key都没有变化。

<!-- 更新前 -->
<div>
  <span className="a">0</span>
  <span className="b">1</span>
</div>


<!-- 更新前1 -->
<div>
  <span className="a">0</span>
  <span className="b">1</span>
  <span className="c">2</span>
</div>


<!-- 更新后 -->
<div>
  <span className="a">0</span>
  <span className="b">2</span>
</div>

这种场景，在Diff的过程，会直接复用oldFiber节点，此时更新后的节点全部遍历了，进入到了newIdx === newChildren.length，如果还存在oldFiber没有遍历(更新前1场景)，则执行deleteRemainingChildren将没有遍历的oldFiber节点都打上Deletion的effectTag

节点类型更新

如下图，节点类型更新，key相同，而elementType不同，不用复用oldFiber，直接创建new Fiber节点

<!-- 更新前 -->
<div>
  <span className="a">0</span>
  <span className="b">1</span>
</div>


<!-- 更新后 -->
<div>
  <span className="a">0</span>
  <div className="b">2</div>
</div>

类型更新的节点跟属性更新的节点之间在执行没有太大的区别，都是在oldFiber节点打上Deletion的effectTag，只是在执行的顺序上有所不同。

我们知道，React Diff 的最终目的是将对比出来具有effectTag的Fiber节点生成一个effectList链表，在commit阶段遍历此链表进行DOM操作。

接下来看下在节点更新中属性更新和类型更新在生成effectList有什么不同？

节点属性更新 - Fiber树

可以看到，当节点属性更新之后，workInProgress Fiber中更新的节点都复用了current Fiber中的节点，因此workInProgress Fiber中的每一个节点都会指向(alternate)对应的current Fiber节点。

当所有的节点都被复用之后（新老节点的位置、个数一致），在Diff 算法的过程中是不会产生EffectList的，如下图：

上图是render阶段 - completeWork生成的effectList，这里具有effectTag的节点就是div Fiber节点，在completeWork阶段会判断如果workInProgress Fiber节点具有effectTag的话，就会将其挂载在其return Fiber 节点的firstEffect和lastEffect属性上。

这里可以看到在completeWork阶段处理effectList链表的源码

节点类型更新 - Fiber树

可以看到，当节点类型更新之后，workInProgress Fiber是不会复用oldFiber的，因此更改的div Fiber是不会有alternate指向其current Fiber的。

由于更新了节点类型，就会产生effectTag，oldFiber span节点就会被打上Deletion的effectTag，从而在Diff 算法的过程中产生EffectList。

如下图：

在第一轮遍历中，div Fiber不能复用span Fiber节点，因此新创建了Fiber节点，只有为span Fiber节点打上Deletion的EffectTag，同时在其return Fiber节点上产生EffectList（上图左侧）。之后在completeWork阶段会在其基础上继续生成带有EffectTag的effectList（上图右侧）。

这里可以看到在Diff 算法的过程中产生EffectList的源码

节点增加

如下图：新增了一个子节点

<!-- 更新前 -->
<div>
  <span className="a">0</span>
  <span className="b">1</span>
</div>


<!-- 更新后 -->
<div>
  <span className="a">0</span>
  <div className="b">1</div>
  <span className="c">2</span>
</div>

这里，第一轮循环结束之后，会继续遍历newChildren，生成第三个span Fiber节点，为其打上Placement的effectTag，然后生成effectList。

下图为节点增加的双缓存Fiber树

同理，不能复用的节点或者新增的节点都会生成Fiber节点，都没有alternate指向其current Fiber。

下面看下节点增加最后产生的effectList

新增的fiber节点打上了effectTag，在completeWork中产生了diff 算法之后的effectList。

节点减少

如下图：新增了一个子节点

<!-- 更新前 -->
<div>
  <span className="a">0</span>
  <span className="b">1</span>
</div>


<!-- 更新后 -->
<div>
  <span className="a">0</span>
</div>

此时，newChildren遍历结束，oldFiber还有的话，需要为每一个oldFiber节点打上Deletion的effectTag，然后产生effectList。

下图为节点减少的双缓存Fiber树

下面看下节点增加最后产生的effectList

节点移动

如下图：节点的位置发生了变化

<!-- 更新前 -->
<div>
  <span className="a">0</span>
  <span className="b">1</span>
</div>


<!-- 更新后 -->
<div>
  <span className="b">1</span>
  <span className="a">0</span>
</div>

这里，只是节点的位置发生了变化，因此节点是可以复用的，如下图双缓存Fiber树

这里问题来了，如何对位置变化的Fiber 打上effectTag呢？

这个例子中，span a和span b元素的位置发生了变化，简单的DOM操作的话，直接获取span a元素的dom对象，通过appendChildren直接插入到div中。

在diff的过程中，会将span a元素的Fiber对象打上Placement 的EffectTag，这个过程就是位置变化对比新旧fiber的过程。

如下图：

在遍历newChildren的过程中，lastPlaceIndex会保存可复用节点的上一次位置索引index，初始值为0

  • 如果可复用节点的索引oldIndex < lastPlaceIndex，那么当前newChildren[newIdx]的Fiber节点会打上Placement的effectTag的tag，表示该节点需要移动；同时下一次循环复用该lastPlaceIndex.
  • 如果可复用节点的索引oldIndex >= lastPlaceIndex, 那么用oldIndex更新lastPlaceIndex，表示该节点此次不需要移动。

这里可以看到此次Diff的位置对比源码，在placeChild方法中。

最后，关于多节点的diff还有其他的场景，上面罗列了一些比较常见的方式。其中最重要的就是判断新老节点是否能够复用，节点的effectTag以及effectList的产生。

而最终产生的effectList会在commit阶段遍历，从而更新真实的DOM节点。

总结

React diff算法是在被限制场景下进行的高效对比算法，在双缓存 Fiber树的前提下，构建workInProgress Fiber树完全是在内存中进行的，这也是diff操作的一个优点，并不会干扰页面的呈现。

React diff算法也是render阶段（也被称为协调过程）中最重要的一环，在mount阶段创建workInProgress Fiber树，然后在commit阶段将workInProgress Fiber指向current Fiber树；在update阶段进行diff算法，对比current Fiber节点同级的JSX对象，生成worKInProgress Fiber树，同时产生effectList链表，在commit阶段遍历这条链表，依次执行副作用。

这里React diff算法大致就结束了，在后面会继续深入commit阶段，是如何遍历effectList链表的。