React源码系列(八)：搞定React DIFF设计思想和源码

站长

2023年03月21日 19:29 · 阅读数 66

前言

这是React源码系列专栏的第八篇文章，预计写10篇左右，之前的文章请查看文末，通过本专栏的学习，相信大家可以快速掌握React源码的相关概念以及核心思想，向成为大佬的道路上更近一步；本章我们学习render阶段diff算法的设计思想和源码，本系列源码基于v18.2.0版本；

什么是协调

协调就是通过如 ReactDOM 等类库使虚拟DOM与真实的DOM同步。通俗的讲协调是将虚拟DOM映射到真实DOM的过程。而diff是协调的一个环节，协调是使一致的过程，而Diff是找不同的过程。

diff设计思想

在传统方式中，要找出两棵树不同，需要一一对节点对比，这个过程的算法复杂度是O(n³)。也就是说假如一棵树有100个节点，那么比较一次就需要操作10w次，代价是非常昂贵的。那么是如何简化这个过程的呢？就是将 O (n³) 复杂度转换成 O (n) 复杂度：

若两个组件属于同一个类型，那么它们将拥有相同的 DOM 树形结构；
处于同一层级的一组子节点，可用通过设置 key 作为唯一标识，从而维持各个节点在不同渲染过程中的稳定性。

diff策略总结为以下三点：

diff 算法性能突破的关键点在于“分层对比”；
类型相同的节点才有继续 diff 的必要性；
设置key 属性，重用同一层级内的节点；

分层对比

它只针对相同层级的节点作对比，如下图所示。

React源码系列(八)：搞定React DIFF设计思想和源码

销毁 + 重建的代价是昂贵的，尽量保持 DOM 结构的稳定性。所以React发生了跨层级的节点操作，它只能认为移出子树那一层的组件消失了，对应子树需要被销毁；而移入子树的那一层新增了一个组件，需要重新为其创建一棵子树。

React源码系列(八)：搞定React DIFF设计思想和源码

节点类型判断

在React 中，只有同类型的组件，才有进一步对比的必要性；若参与 Diff 的两个组件类型不同，那么直接放弃比较，原地替换掉旧的节点。只有确认组件类型相同后，React 才会在保留组件对应 DOM 树（或子树）的基础上，尝试向更深层次去 Diff。这样一来，便能够从很大程度上减少 Diff 过程中冗余的递归操作。如下图所示，直接移除span以及后代所有节点，新增p节点及后代节点；

React源码系列(八)：搞定React DIFF设计思想和源码

使用key来保持节点的稳定性

key属性的设置，可以帮我们尽可能重用同一层级内的节点。它就像一个记号一样，帮助记住某一个节点，从而在后续的更新中实现对节点的追踪；

key 是用来帮助 React 识别哪些内容被更改、添加或者删除。key 需要写在用数组渲染出来的元素内部，并且需要赋予其一个稳定的值。稳定在这里很重要，因为如果 key 值发生了变更，React 则会触发 UI 的重渲染。这是一个非常有用的特性。

React源码系列(八)：搞定React DIFF设计思想和源码

这个 key 就是每个节点的唯一标识，有了这个标识之后，当 C 被插入到 B 和 D 之间时，React 并不会再认为 C、D、E 这三个坑位都需要被重建——它会通过识别唯一标识，意识到 D 和 E 并没有发生变化（D 的 ID 仍然是 1，E 的 ID 仍然是 2），而只是被调整了顺序而已。接着，React 便能够轻松地重用它追踪到旧的节点，将 D 和 E 转移到新的位置，并完成对 C 的插入。这样一来，同层级下元素的操作成本便大大降低。

ChildReconciler

在之前章节 React源码系列(六)：render阶段beginWork流程解析讲解了ChildReconciler方法会返回reconcileChildFibers方法，即为diff算法的处理过程。

// react/packages/react-reconciler/src/ReactChildFiber.old.js
function ChildReconciler(shouldTrackSideEffects) {
   function reconcileChildFibers(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    newChild: any,
    lanes: Lanes,
  ): Fiber | null {
     /** ...省略一大段逻辑...**/
  }

  // 将总的 reconcileChildFibers 函数返回
  return reconcileChildFibers;
}

reconcileChildFibers

在render阶段更新Fiber节点时，会调用reconcileChildFibers对比current Fiber和workInProgress Fiber。 reconcileChildFibers中会根据newChild的类型来进入单节点的diff或者多节点diff。

 function reconcileChildFibers(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    newChild: any,
    lanes: Lanes,
  ): Fiber | null {
    /** ...省略...**/

    if (typeof newChild === 'object' && newChild !== null) {
      switch (newChild.$$typeof) {
        case REACT_ELEMENT_TYPE:
          return placeSingleChild(
            // 单节点diff
            reconcileSingleElement(
              returnFiber,
              currentFirstChild,
              newChild,
              lanes,
            ),
          );

           /** ...省略...**/
      }

      if (isArray(newChild)) {
        // 多节点diff
        return reconcileChildrenArray(
          returnFiber,
          currentFirstChild,
          newChild,
          lanes,
        );
      }
    }

    // 删除节点
    return deleteRemainingChildren(returnFiber, currentFirstChild);
  }

单节点diff

单点diff有以下几种情况：

key和type相同表示可以复用节点
key不同直接标记删除节点，新建节点
key相同type不同，标记删除该节点和兄弟节点，新创建节点

function reconcileSingleElement(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    element: ReactElement,
    lanes: Lanes,
  ): Fiber {
    const key = element.key;
    let child = currentFirstChild;
    while (child !== null) {
       // 比较key
      if (child.key === key) {
        const elementType = element.type;
        // Fragment节点类型处理
        if (elementType === REACT_FRAGMENT_TYPE) {
          if (child.tag === Fragment) {
            deleteRemainingChildren(returnFiber, child.sibling);
            const existing = useFiber(child, element.props.children);
            existing.return = returnFiber;
            if (__DEV__) {
              existing._debugSource = element._source;
              existing._debugOwner = element._owner;
            }
            return existing;
          }
        } else {
          if (
            // 比较type
            // 如果新的 ReactElement 和旧 Fiber 的 key 和 type 都相等
            child.elementType === elementType ||
            (__DEV__
              ? isCompatibleFamilyForHotReloading(child, element)
              : false) ||
            (typeof elementType === 'object' &&
              elementType !== null &&
              elementType.$$typeof === REACT_LAZY_TYPE &&
              resolveLazy(elementType) === child.type)
          ) {
            deleteRemainingChildren(returnFiber, child.sibling);
            // 复用之前current树上相对应的fiber，并使用最新的props更新fiber上的pendingProps属性
            const existing = useFiber(child, element.props);
            existing.ref = coerceRef(returnFiber, child, element);
            existing.return = returnFiber;
            if (__DEV__) {
              existing._debugSource = element._source;
              existing._debugOwner = element._owner;
            }
            // type相同则可以复用 返回复用的节点
            return existing;
          }
        }
        // key相同，type不同则把fiber及和兄弟fiber标记删除
        deleteRemainingChildren(returnFiber, child);

        // type不同跳出
        break;
      } else {
        // key不同直接标记删除该节点
        deleteChild(returnFiber, child);
      }
      child = child.sibling;
    }

    // 当key或者类型不相等时，会根据新创建的React element元素创建新的Fiber节点
    if (element.type === REACT_FRAGMENT_TYPE) {
      const created = createFiberFromFragment(
        element.props.children,
        returnFiber.mode,
        lanes,
        element.key,
      );
      created.return = returnFiber;
      return created;
    } else {
      const created = createFiberFromElement(element, returnFiber.mode, lanes);
      created.ref = coerceRef(returnFiber, currentFirstChild, element);
      created.return = returnFiber;
      return created;
    }
  }

多节点diff

多节点diff有三次for循环遍历（循环可以跳出）

第一次遍历处理节点的更新（包括props更新和type更新和删除）；
第二次遍历处理其他的情况（节点新增），例如老节点没了，新节点还有，逐个新增即可；
第三次处理位节点置改变；

第一次遍历

第一次遍历处理节点的更新（包括props更新和type更新和删除），会经历以下4种情况：

key不同，第一次循环结束；
newChildren或者oldFiber遍历完，第一次循环结束；
key同type不同，标记oldFiber为DELETION；
key相同type相同则可以复用；

newChildren遍历完，oldFiber没遍历完，在第一次遍历完成之后将oldFiber中没遍历完的节点标记为DELETION；

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

  /** ...省略... **/

 let oldFiber = currentFirstChild;
 // 记录上次插入节点的位置，判断节点是否需要移动
 let lastPlacedIndex = 0;
 // newChildren是数组，newIdx就是遍历数组用的下标
 let newIdx = 0;
 let nextOldFiber = null;

  // 第一次遍历新老VDOM都是从左边开始遍历，按位比较，如果节点可以复用，那么都往后移一位，否则中止本轮循环
  for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
     // oldFiber的下标大于新的，本轮循环中止
    if (oldFiber.index > newIdx) {
      nextOldFiber = oldFiber;
      oldFiber = null;
    } else {
      nextOldFiber = oldFiber.sibling;
    }
    // 通过 updateSlot 来 diff oldFiber 和新的 child，生成新的 Fiber
    const newFiber = updateSlot(
      returnFiber,
      oldFiber,
      newChildren[newIdx],
      lanes
    );
     // newFiber 为 null 说明不可复用，退出第一轮的循环
    if (newFiber === null) {
      if (oldFiber === null) {
        oldFiber = nextOldFiber;
      }
      break;
    }
    if (shouldTrackSideEffects) {
      if (oldFiber && newFiber.alternate === null) {
        deleteChild(returnFiber, oldFiber);
      }
    }
    // 记录复用的 oldFiber 的 index
    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
    if (previousNewFiber === null) {
      resultingFirstChild = newFiber;
    } else {
      previousNewFiber.sibling = newFiber;
    }
    previousNewFiber = newFiber;
    oldFiber = nextOldFiber;
  }
  // 如果newIdx === newChildren.length，证明经过上轮循环，新节点已经遍历完了，那么如果还有剩下的老节点，删除即可
  if (newIdx === newChildren.length) {
    deleteRemainingChildren(returnFiber, oldFiber);
    if (getIsHydrating()) {
      const numberOfForks = newIdx;
      pushTreeFork(returnFiber, numberOfForks);
    }
    return resultingFirstChild;
  }
  
  /** ...省略... **/
}

第二次遍历

第二次遍历处理其他的情况（节点新增），例如老节点没了，新节点还有，逐个新增即可，会经历以下3种情况：

newChildren和oldFiber都遍历完：多节点diff过程结束；
newChildren没遍历完，oldFiber遍历完，将剩下的newChildren的节点标记为Placement；
newChildren和oldFiber没遍历完，则进入节点移动的逻辑；

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

  /** ...省略第一遍for相关逻辑... **/

  // 如果老节点没了，新节点还有，那么新节点逐个新增即可
  if (oldFiber === null) {
    for (; newIdx < newChildren.length; newIdx++) {
      // 遍历剩下的 child，通过 createChild 创建新的 fiber
      const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
      if (newFiber === null) {
        continue;
      }
      // 处理dom移动，记录 index
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
    }
    if (getIsHydrating()) {
      const numberOfForks = newIdx;
      pushTreeFork(returnFiber, numberOfForks);
    }
    return resultingFirstChild;
  }

  /** ...省略... **/
}

第三次遍历

第三次遍历处理节点位置改变；

function reconcileChildrenArray(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChildren: Array<*>,
  lanes: Lanes
): Fiber | null {
  
  /** ...省略第一个和第二个for相关逻辑... **/

  // oldFiber 和 newChildren 都未遍历完
  // mapRemainingChildren 生成一个以 oldFiber 的 key 为 key， oldFiber 为 value 的 map
  const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
  // 对剩下的 newChildren 进行遍历
  for (; newIdx < newChildren.length; newIdx++) {
    // 找到 mapRemainingChildren 中 key 相等的 fiber, 创建新 fiber 复用
    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
          );
        }
      }
      // 处理dom移动，记录 index
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
    }
  }

  // 发现老节点中还有没被复用的，打上 Deletion 副作用标签
  if (shouldTrackSideEffects) {
    existingChildren.forEach((child) => deleteChild(returnFiber, child));
  }

  if (getIsHydrating()) {
    const numberOfForks = newIdx;
    pushTreeFork(returnFiber, numberOfForks);
  }
  return resultingFirstChild;
}

实用场景举例1

// old DOM
<ul>
  <li key="A">A</li>
  <li key="B">B</li>
  <li key="C">C</li>
  <li key="D">D</li>
</ul>


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

// new DOM
<ul>
  <li key="A">A</li>
  <li key="C">C</li>
  <li key="D">D</li>
  <li key="B">B</li>
</ul>

如上面的例子，会经历以下5种情况：

newChild中第一个位置的A和oldFiber第一个位置的A，key相同可复用，初始化lastPlacedIndex=0
newChild中第二个位置的C和oldFiber第二个位置的B，key不同跳出第一次循环，将oldFiber中的BCD保存在map中
newChild中第二个位置的C在oldFiber中的index=2 > lastPlacedIndex=0不需要移动，lastPlacedIndex=2
newChild中第三个位置的D在oldFiber中的index=3 > lastPlacedIndex=2不需要移动，lastPlacedIndex=3
newChild中第四个位置的B在oldFiber中的index=1 < lastPlacedIndex=3,移动到最后

React源码系列(八)：搞定React DIFF设计思想和源码

实用场景举例2

// old DOM
<ul>
  <li key="A">A</li>
  <li key="B">B</li>
  <li key="C">C</li>
  <li key="D">D</li>
</ul>


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

// new DOM
<ul>
  <li key="D">D</li>
  <li key="A">A</li>
  <li key="B">B</li>
  <li key="C">C</li>
</ul>

如上面的例子，会经历以下5种情况：

newChild中第一个位置的D和oldFiber第一个位置的A，key不相同不可复用，将oldFiber中的ABCD保存在map中，lastPlacedIndex=0
newChild中第一个位置的D在oldFiber中的index=3 > lastPlacedIndex=0，不需要移动，lastPlacedIndex=3
newChild中第二个位置的A在oldFiber中的index=0 < lastPlacedIndex=3，移动到最后
newChild中第三个位置的B在oldFiber中的index=1 < lastPlacedIndex=3，移动到最后
newChild中第四个位置的C在oldFiber中的index=2 < lastPlacedIndex=3，移动到最后

React源码系列(八)：搞定React DIFF设计思想和源码

多节点diff完整代码

function reconcileChildrenArray(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChildren: Array<*>,
  lanes: Lanes
): Fiber | null {
  let oldFiber = currentFirstChild;
  // 记录上次插入节点的位置，判断节点是否需要移动
  let lastPlacedIndex = 0;
  // newChildren是数组，newIdx就是遍历数组用的下标
  let newIdx = 0;
  let nextOldFiber = null;

  // 第一次遍历新老VDOM都是从左边开始遍历，按位比较，如果节点可以复用，那么都往后移一位，否则中止本轮循环
  for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
    // oldFiber的下标大于新的，本轮循环中止
    if (oldFiber.index > newIdx) {
      nextOldFiber = oldFiber;
      oldFiber = null;
    } else {
      nextOldFiber = oldFiber.sibling;
    }
    // 通过 updateSlot 来 diff oldFiber 和新的 child，生成新的 Fiber
    const newFiber = updateSlot(
      returnFiber,
      oldFiber,
      newChildren[newIdx],
      lanes
    );
    // newFiber 为 null 说明不可复用，退出第一轮的循环
    if (newFiber === null) {
      if (oldFiber === null) {
        oldFiber = nextOldFiber;
      }
      break;
    }
    if (shouldTrackSideEffects) {
      if (oldFiber && newFiber.alternate === null) {
        deleteChild(returnFiber, oldFiber);
      }
    }
    // 记录复用的 oldFiber 的 index
    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
    if (previousNewFiber === null) {
      resultingFirstChild = newFiber;
    } else {
      previousNewFiber.sibling = newFiber;
    }
    previousNewFiber = newFiber;
    oldFiber = nextOldFiber;
  }
  // 如果newIdx === newChildren.length，证明经过上轮循环，新节点已经遍历完了，那么如果还有剩下的老节点，删除即可
  if (newIdx === newChildren.length) {
    deleteRemainingChildren(returnFiber, oldFiber);
    if (getIsHydrating()) {
      const numberOfForks = newIdx;
      pushTreeFork(returnFiber, numberOfForks);
    }
    return resultingFirstChild;
  }

  // 如果老节点没了，新节点还有，那么新节点逐个新增即可
  if (oldFiber === null) {
    for (; newIdx < newChildren.length; newIdx++) {
      // 遍历剩下的 child，通过 createChild 创建新的 fiber
      const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
      if (newFiber === null) {
        continue;
      }
      // 处理dom移动，记录 index
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
    }
    if (getIsHydrating()) {
      const numberOfForks = newIdx;
      pushTreeFork(returnFiber, numberOfForks);
    }
    return resultingFirstChild;
  }

  // oldFiber 和 newChildren 都未遍历完
  // mapRemainingChildren 生成一个以 oldFiber 的 key 为 key， oldFiber 为 value 的 map
  const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
  // 对剩下的 newChildren 进行遍历
  for (; newIdx < newChildren.length; newIdx++) {
    // 找到 mapRemainingChildren 中 key 相等的 fiber, 创建新 fiber 复用
    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
          );
        }
      }
      // 处理dom移动，记录 index
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
    }
  }

  // 发现老节点中还有没被复用的，打上 Deletion 副作用标签
  if (shouldTrackSideEffects) {
    existingChildren.forEach((child) => deleteChild(returnFiber, child));
  }

  if (getIsHydrating()) {
    const numberOfForks = newIdx;
    pushTreeFork(returnFiber, numberOfForks);
  }
  return resultingFirstChild;
}

小结

本章我们学习了diff的设计思想和源码，接下来的文章将进入commit阶段流程分析，欢迎继续跟随本专栏一起学习；

参考链接

深入浅出搞定React

React源码系列

转载自:https://juejin.cn/post/7212548256944767034