关于react.js: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 是针对新 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;
  }
}

针对 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

关于react.js:React源码分析之diff核心算法

前言

reconcileSingleElement

reconcileChildrenArray

placeChild

总结