title: 调和算法

React 算法之调和算法

概念

调和函数(源码)是在fiber树构(对比更新)过程中对旧fiber节点与新reactElement进行比较, 判定旧fiber节点是否可以复用的一个比较函数.

调和函数仅是fiber树构造过程中的一个环节, 所以在深入理解这个函数之前, 建议对fiber树构造有一个宏观的理解(可以参考前文fiber 树构造(初次创建), fiber 树构造(对比更新)), 本节重点探讨其算法的实现细节.

它的主要作用:

  1. 给新增,移动,和删除节点设置fiber.flags(新增, 移动: Placement, 删除: Deletion)
  2. 如果是需要删除的fiber, 除了自身打上Deletion之外, 还要将其添加到父节点的effects链表中(正常副作用队列的处理是在completeWork函数, 但是该节点(被删除)会脱离fiber树, 不会再进入completeWork阶段, 所以在beginWork阶段提前加入副作用队列).

特性

算法复杂度低, 从上至下比较整个树形结构, 时间复杂度被缩短到 O(n)

基本原理

  1. 比较对象: fiber对象与ReactElement对象相比较.
    • 注意: 此处有一个误区, 并不是两棵 fiber 树相比较, 而是旧fiber对象与新ReactElement对象向比较, 结果生成新的fiber子节点.
    • 可以理解为输入ReactElement, 经过reconcileChildren()之后, 输出fiber.
  2. 比较方案:
    • 单节点比较
    • 可迭代节点比较

单节点比较

单节点的逻辑比较简明, 先直接看源码:

  1. // 只保留主干逻辑
  2. function reconcileSingleElement(
  3.   returnFiber: Fiber,
  4.   currentFirstChild: Fiber | null,
  5.   element: ReactElement,
  6.   lanes: Lanes,
  7. ): Fiber {
  8.   const key = element.key;
  9.   let child = currentFirstChild;
  11.   while (child !== null) {
  12.     // currentFirstChild !== null, 表明是对比更新阶段
  13.     if (child.key === key) {
  14.       // 1. key相同, 进一步判断 child.elementType === element.type
  15.       switch (child.tag) {
  16.         // 只看核心逻辑
  17.         default: {
  18.           if (child.elementType === element.type) {
  19.             // 1.1 已经匹配上了, 如果有兄弟节点, 需要给兄弟节点打上Deletion标记
  20.             deleteRemainingChildren(returnFiber, child.sibling);
  21.             // 1.2 构造fiber节点, 新的fiber对象会复用current.stateNode, 即可复用DOM对象
  22.             const existing = useFiber(child, element.props);
  23.             existing.ref = coerceRef(returnFiber, child, element);
  24.             existing.return = returnFiber;
  25.             return existing;
  26.           }
  27.           break;
  28.         }
  29.       }
  30.       // Didn't match. 给当前节点点打上Deletion标记
  31.       deleteRemainingChildren(returnFiber, child);
  32.       break;
  33.     } else {
  34.       // 2. key不相同, 匹配失败, 给当前节点打上Deletion标记
  35.       deleteChild(returnFiber, child);
  36.     }
  37.     child = child.sibling;
  38.   }
  40.   {
  41.     // ...省略部分代码, 只看核心逻辑
  42.   }
  44.   // 新建节点
  45.   const created = createFiberFromElement(element, returnFiber.mode, lanes);
  46.   created.ref = coerceRef(returnFiber, currentFirstChild, element);
  47.   created.return = returnFiber;
  48.   return created;
  49. }
  1. 如果是新增节点, 直接新建 fiber, 没有多余的逻辑
  2. 如果是对比更新
    • 如果key和type都相同(即: ReactElement.key === Fiber.key 且 Fiber.elementType === ReactElement.type), 则复用
    • 否则新建

注意: 复用过程是调用useFiber(child, element.props)创建新的fiber对象, 这个新fiber对象.stateNode = currentFirstChild.stateNode, 即stateNode属性得到了复用, 故 DOM 节点得到了复用.

可迭代节点比较(数组类型, [Symbol.iterator]=fn,[@@iterator]=fn)

可迭代节点比较, 在源码中被分为了 2 个部分:

  1. function reconcileChildFibers(
  2.   returnFiber: Fiber,
  3.   currentFirstChild: Fiber | null,
  4.   newChild: any,
  5.   lanes: Lanes,
  6. ): Fiber | null {
  7.   if (isArray(newChild)) {
  8.     return reconcileChildrenArray(
  9.       returnFiber,
  10.       currentFirstChild,
  11.       newChild,
  12.       lanes,
  13.     );
  14.   }
  15.   if (getIteratorFn(newChild)) {
  16.     return reconcileChildrenIterator(
  17.       returnFiber,
  18.       currentFirstChild,
  19.       newChild,
  20.       lanes,
  21.     );
  22.   }
  23. }

其中reconcileChildrenArray函数(针对数组类型)和reconcileChildrenIterator(针对可迭代类型)的核心逻辑几乎一致, 下文将分析reconcileChildrenArray()函数. 如果是新增节点, 所有的比较逻辑都无法命中, 只有对比更新过程, 才有实际作用, 所以下文重点分析对比更新的情况.

  1. function reconcileChildrenArray(
  2.   returnFiber: Fiber,
  3.   currentFirstChild: Fiber | null,
  4.   newChildren: Array<*>,
  5.   lanes: Lanes,
  6. ): Fiber | null {
  7.   let resultingFirstChild: Fiber | null = null;
  8.   let previousNewFiber: Fiber | null = null;
  10.   let oldFiber = currentFirstChild;
  11.   let lastPlacedIndex = 0;
  12.   let newIdx = 0;
  13.   let nextOldFiber = null;
  14.   // 1. 第一次循环: 遍历最长公共序列(key相同), 公共序列的节点都视为可复用
  15.   for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
  16.     // 后文分析
  17.   }
  19.   if (newIdx === newChildren.length) {
  20.     // 如果newChildren序列被遍历完, 那么oldFiber序列中剩余节点都视为删除(打上Deletion标记)
  21.     deleteRemainingChildren(returnFiber, oldFiber);
  22.     return resultingFirstChild;
  23.   }
  25.   if (oldFiber === null) {
  26.     // 如果oldFiber序列被遍历完, 那么newChildren序列中剩余节点都视为新增(打上Placement标记)
  27.     for (; newIdx < newChildren.length; newIdx++) {
  28.       // 后文分析
  29.     }
  30.     return resultingFirstChild;
  31.   }
  33.   // ==================分割线==================
  34.   const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
  36.   // 2. 第二次循环: 遍历剩余非公共序列, 优先复用oldFiber序列中的节点
  37.   for (; newIdx < newChildren.length; newIdx++) {}
  39.   if (shouldTrackSideEffects) {
  40.     // newChildren已经遍历完, 那么oldFiber序列中剩余节点都视为删除(打上Deletion标记)
  41.     existingChildren.forEach(child => deleteChild(returnFiber, child));
  42.   }
  44.   return resultingFirstChild;
  45. }

reconcileChildrenArray函数源码看似很长, 梳理其主干之后, 其实非常清晰.

通过形参, 首先明确比较对象是currentFirstChild: Fiber | null和newChildren: Array<*>:

  • currentFirstChild: 是一个fiber节点, 通过fiber.sibling可以将兄弟节点全部遍历出来. 所以可以将currentFirstChild理解为链表头部, 它代表一个序列, 源码中被记为oldFiber.
  • newChildren: 是一个数组, 其中包含了若干个ReactElement对象. 所以newChildren也代表一个序列.

所以reconcileChildrenArray实际就是 2 个序列之间的比较(链表oldFiber和数组newChildren), 最后返回合理的fiber序列.

上述代码中, 以注释分割线为界限, 整个核心逻辑分为 2 步骤:

  1. 第一次循环: 遍历最长公共序列(key 相同), 公共序列的节点都视为可复用
    • 如果newChildren序列被遍历完, 那么oldFiber序列中剩余节点都视为删除(打上Deletion标记)
    • 如果oldFiber序列被遍历完, 那么newChildren序列中剩余节点都视为新增(打上Placement标记)
  2. 第二次循环: 遍历剩余非公共序列, 优先复用 oldFiber 序列中的节点
    • 在对比更新阶段(非初次创建fiber, 此时shouldTrackSideEffects被设置为true). 第二次循环遍历完成之后, oldFiber序列中没有匹配上的节点都视为删除(打上Deletion标记)

假设有如下图所示 2 个初始化序列:

React 算法之调和算法 - 图1

接下来第一次循环, 会遍历公共序列A,B, 生成的 fiber 节点fiber(A), fiber(B)可以复用.

React 算法之调和算法 - 图2

最后第二次循环, 会遍历剩余序列E,C,X,Y:

  • 生成的 fiber 节点fiber(E), fiber(C)可以复用. 其中fiber(C)节点发生了位移(打上Placement标记).
  • fiber(X), fiber(Y)是新增(打上Placement标记).
  • 同时oldFiber序列中的fiber(D)节点确定被删除(打上Deletion标记).

React 算法之调和算法 - 图3

整个主干逻辑就介绍完了, 接下来贴上完整源码

第一次循环

  1. // 1. 第一次循环: 遍历最长公共序列(key相同), 公共序列的节点都视为可复用
  2. for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
  3.   if (oldFiber.index > newIdx) {
  4.     nextOldFiber = oldFiber;
  5.     oldFiber = null;
  6.   } else {
  7.     nextOldFiber = oldFiber.sibling;
  8.   }
  9.   // new槽位和old槽位进行比较, 如果key不同, 返回null
  10.   // key相同, 比较type是否一致. type一致则执行useFiber(update逻辑), type不一致则运行createXXX(insert逻辑)
  11.   const newFiber = updateSlot(
  12.     returnFiber,
  13.     oldFiber,
  14.     newChildren[newIdx],
  15.     lanes,
  16.   );
  18.   if (newFiber === null) {
  19.     // 如果返回null, 表明key不同. 无法满足公共序列条件, 退出循环
  20.     if (oldFiber === null) {
  21.       oldFiber = nextOldFiber;
  22.     }
  23.     break;
  24.   }
  25.   if (shouldTrackSideEffects) {
  26.     // 若是新增节点, 则给老节点打上Deletion标记
  27.     if (oldFiber && newFiber.alternate === null) {
  28.       deleteChild(returnFiber, oldFiber);
  29.     }
  30.   }
  32.   // lastPlacedIndex 记录被移动的节点索引
  33.   // 如果当前节点可复用, 则要判断位置是否移动.
  34.   lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
  36.   // 更新resultingFirstChild结果序列
  37.   if (previousNewFiber === null) {
  38.     resultingFirstChild = newFiber;
  39.   } else {
  40.     previousNewFiber.sibling = newFiber;
  41.   }
  42.   previousNewFiber = newFiber;
  43.   oldFiber = nextOldFiber;
  44. }

第二次循环

  1. // 1. 将第一次循环后, oldFiber剩余序列加入到一个map中. 目的是为了第二次循环能顺利的找到可复用节点
  2. const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
  4. // 2. 第二次循环: 遍历剩余非公共序列, 优先复用oldFiber序列中的节点
  5. for (; newIdx < newChildren.length; newIdx++) {
  6.   const newFiber = updateFromMap(
  7.     existingChildren,
  8.     returnFiber,
  9.     newIdx,
  10.     newChildren[newIdx],
  11.     lanes,
  12.   );
  13.   if (newFiber !== null) {
  14.     if (shouldTrackSideEffects) {
  15.       if (newFiber.alternate !== null) {
  16.         // 如果newFiber是通过复用创建的, 则清理map中对应的老节点
  17.         existingChildren.delete(newFiber.key === null ? newIdx : newFiber.key);
  18.       }
  19.     }
  20.     lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
  21.     // 更新resultingFirstChild结果序列
  22.     if (previousNewFiber === null) {
  23.       resultingFirstChild = newFiber;
  24.     } else {
  25.       previousNewFiber.sibling = newFiber;
  26.     }
  27.     previousNewFiber = newFiber;
  28.   }
  29. }
  30. // 3. 善后工作, 第二次循环完成之后, existingChildren中剩余的fiber节点就是将要被删除的节点, 打上Deletion标记
  31. if (shouldTrackSideEffects) {
  32.   existingChildren.forEach(child => deleteChild(returnFiber, child));
  33. }

结果

无论是单节点还是可迭代节点的比较, 最终的目的都是生成下级子节点. 并在reconcileChildren过程中, 给一些有副作用的节点(新增, 删除, 移动位置等)打上副作用标记, 等待 commit 阶段(参考fiber 树渲染)的处理.

总结

本节介绍了 React 源码中, fiber构造循环阶段用于生成下级子节点的reconcileChildren函数(函数中的算法被称为调和算法), 并演示了可迭代节点比较的图解示例. 该算法十分巧妙, 其核心逻辑把newChildren序列分为 2 步遍历, 先遍历公共序列, 再遍历非公共部分, 同时复用oldFiber序列中的节点.