React源码分析之diff核心算法

前言

• React的diff算法是在render的beginWork阶段中进行处理
• beginWork是在向下深度遍历fiber树时会对途径的每个节点进行状态处理和进行diff对比
• 首先diff的入口是在reconcileChildFibers中，然后会根据type来判断使用哪种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(
            reconcileSingleElement(
              returnFiber,
              currentFirstChild,
              newChild,
              lanes,
            ),
          );··
        case REACT_PORTAL_TYPE:
          // ...
        case REACT_LAZY_TYPE:
          //...
      }
  
      if (isArray(newChild)) {
        return reconcileChildrenArray(
          returnFiber,
          currentFirstChild,
          newChild,
          lanes,
        );
      }
  
      if (getIteratorFn(newChild)) {
        //...
      }
    }
    // ...
  }

• 我在本篇会针对两种较常用的diff函数进行分析
  • reconcileSingleElement
  • reconcileChildrenArray

reconcileSingleElement

• reconcileSingleElement是针对新newChild是单节点，而oldChild单节点或者是多节点就无法确定了，所以在此diff算法中就会对旧节点进行遍历，然后删除不匹配的oldFiber

  function reconcileSingleElement(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    element: ReactElement
    lanes: Lanes,
  ): Fiber {
    const key = element.key;
    let child = currentFirstChild;
    /**
      * 遍历旧节点，找到与newChild相同key的节点，不匹配的删除
      * 针对匹配的oldFiber, 用newChild中新节点的props来生成新的fiber节点
      */
    while (child !== null) {
      if (child.key === key) {
        const elementType = element.type;
        /**
          * 通过useFiber创建一个新的Fiber
          * 如果element是一个Fragment，则以element.props.children建立Fiber
          * 将returnFiber赋给新的fiber的return字段，然后返回这个新的fiber
          */·
        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 (
            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);
            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;
            }
            return existing;
          }
        }
        // Didn't match.
        deleteRemainingChildren(returnFiber, child);
        break;
      } else {
        // key不相同就删除
        deleteChild(returnFiber, child);
      }
      child = child.sibling;
    }
  
    // 如果没有命中一个key，则通过createFiberFormElement或CreateFiberFormFragment创建一个新的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;
    }
  }

reconcileChildrenArray

• 针对newChild是多节点的情况就需要调用reconcileChildrenArray进行diff操作

• 多节点会有四种可能性的变化：删除、新增、位移、更新

• reconcileChildrenArray针对这四种变化，首先会处理的是更新，当出现无法匹配的情况时，就会根据遍历的情况来判断是否处理删除或者新增，然后最后会根据情况处理位移

• 因为fiber是单向链表，所以reconcileChildrenArray的遍历不是双端遍历

• 首先第一轮遍历，是处理节点更新

  for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
    // newChildren遍历完了，oldFiber没有遍历完，中断遍历
    if (oldFiber.index > newIdx) {
      nextOldFiber = oldFiber;
      oldFiber = null;
    } else {
      // 记录oldFiber的下一个节点
      nextOldFiber = oldFiber.sibling;
    }
    // 更新节点，如果节点没有匹配上，就会返回null
    const newFiber = updateSlot(
      returnFiber,
      oldFiber,
      newChildren[newIdx],
      lanes,
    );
    // newFiber为null说明节点没有匹配上，中断遍历
    if (newFiber === null) {
      // oldFiber为null说明oldFiber也遍历完了
      if (oldFiber === null) {
        oldFiber = nextOldFiber;
      }
      break;
    }
  
    /**
     * shouldTrackSideEffects为true表示是更新过程
     * mountChildFibers = ChildReconciler(false);
     * reconcileChildFibers = ChildReconciler(true);
     * ChildReconciler接收的就是shouldTrackSideEffects
     */
    if (shouldTrackSideEffects) {
      if (oldFiber && newFiber.alternate === null) {
        // 新节点没有现有节点，需要删除
        deleteChild(returnFiber, oldFiber);
      }
    }
    // 记录固定节点的位置
    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
  
    // 将新节点拼接成以sibling为指针的单向链表
    if (previousNewFiber === null) {
      resultingFirstChild = newFiber;
    } else {
      previousNewFiber.sibling = newFiber;
    }
    previousNewFiber = newFiber;
    oldFiber = nextOldFiber;
  }

• 遍历完匹配的节点后，就判断新节点是否遍历完，如果遍历完，那么剩余的oldFiber都是要删除的

  if (newIdx === newChildren.length) {
    deleteRemainingChildren(returnFiber, oldFiber);
    if (getIsHydrating()) {
      const numberOfForks = newIdx;
      pushTreeFork(returnFiber, numberOfForks);
    }
    return resultingFirstChild;
  }

• 如果新旧点没有遍历完，就判断旧fiber链是否遍历完，如果遍历完那么剩余的新节点全部作为新fiber插入

  if (oldFiber === null) {
    for (; newIdx < newChildren.length; newIdx++) {
      // 创建新fiber节点
      const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
      if (newFiber === null) {
        continue;
      }
  
      // 记录固定节点
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
  
      // 将新fiber拼接成以sibling为指针的单向链表
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
    }
    if (getIsHydrating()) {
      const numberOfForks = newIdx;
      pushTreeFork(returnFiber, numberOfForks);
    }
    return resultingFirstChild;
  }

• 执行到这一步，说明新旧节点都没有遍历完，就说明存在有位移的未知序列

  // 首先创建一个以oldFiber key为键，值为oldFiber的map
  const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
  
  for (; newIdx < newChildren.length; newIdx++) {
    // 然后根据map中的oldFiber创建新fiber
    const newFiber = updateFromMap(
      existingChildren,
      returnFiber,
      newIdx,
      newChildren[newIdx],
      lanes,
    );
    if (newFiber !== null) {
      if (shouldTrackSideEffects) {
        if (newFiber.alternate !== null) {
          // 如果newFiber.alternate不为null，说明是根据oldFiber创建的，那么就需要在map中删除oldFiber
          existingChildren.delete(
            newFiber.key === null ? newIdx : newFiber.key,
          );
        }
      }
  
      // 根据lastPlacedIndex判断是否移动节点
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
  
      // 将新fiber拼接成以sibling为指针的单向链表
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
    }
  }
  
  if (shouldTrackSideEffects) {
    // 删除剩余的oldFiber
    existingChildren.forEach(child => deleteChild(returnFiber, child));
  }

• 移动节点的核心是在placeChild这个函数中，如果当前正在遍历的节点的oldIndex是在lastPlacedIndex的右边，就说明它的位置没变化，因为旧节点中就处于右边，新节点中也处于右边。

  • 例如：old：A -> B -> C -> D，new：D -> A -> B -> C
  • 遍历到D时，lastPlacedIndex = D的oldIndex = 3
  • 然后遍历到A时，A的oldIndex为0，小于3，说明A在旧序列中肯定不是D的右边，所以A肯定产生了位移

    function placeChild(
      newFiber: Fiber,
      lastPlacedIndex: number,
      newIndex: number,
    ): number {
      newFiber.index = newIndex;
      if (!shouldTrackSideEffects) {
        newFiber.flags |= Forked;
        return lastPlacedIndex;
      }
      const current = newFiber.alternate;
      if (current !== null) {
        const oldIndex = current.index;
        if (oldIndex < lastPlacedIndex) {
          // 小于lastPlacedIndex 产生了位移
          newFiber.flags |= Placement | PlacementDEV;
          return lastPlacedIndex;
        } else {
          // 没有位移，返回当前的oldIndex
          return oldIndex;
        }
      } else {
        newFiber.flags |= Placement | PlacementDEV;
        return lastPlacedIndex;
      }
    }

总结

• 针对单节点的diff，会遍历oldFiber链，如果有匹配的fiber，就以匹配的生成新fiber，如果没有就新建一个fiber，然后删除不匹配的fiber
• 针对多节点diff
  • 首先是从头向尾遍历，针对复用的fiber进行更新，如果无法复用就中断遍历
  • 然后判断新旧节点的遍历情况，来判断是否新增或者删除
  • 如果都没有遍历完，就创建一个mapMap<old key, old Fiber>，然后遍历新节点，基于map来创建新fiber，然后根据lastPlacedIndex来判断是否产生了位移，遍历完最后删除剩余的oldFiber