• 【React源码】(十八)React 算法之调和算法

    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.  
    3. function reconcileSingleElement(
    5. returnFiber: Fiber,
    7. currentFirstChild: Fiber | null,
    9. element: ReactElement,
    11. lanes: Lanes,
    13. ): Fiber {
    14.  
    15. const key = element.key;
    16.  
    17. let child = currentFirstChild;
    18.  
    19. while (child !== null) {
    20.  
    21. // currentFirstChild !== null, 表明是对比更新阶段
    22.  
    23. if (child.key === key) {
    24.  
    25. // 1. key相同, 进一步判断 child.elementType === element.type
    26.  
    27. switch (child.tag) {
    28.  
    29. // 只看核心逻辑
    30.  
    31. default: {
    32.  
    33. if (child.elementType === element.type) {
    34.  
    35. // 1.1 已经匹配上了, 如果有兄弟节点, 需要给兄弟节点打上Deletion标记
    36.  
    37. deleteRemainingChildren(returnFiber, child.sibling);
    38.  
    39. // 1.2 构造fiber节点, 新的fiber对象会复用current.stateNode, 即可复用DOM对象
    40.  
    41. const existing = useFiber(child, element.props);
    42.  
    43. existing.ref = coerceRef(returnFiber, child, element);
    44.  
    45. existing.return = returnFiber;
    46.  
    47. return existing;
    48.  
    49. }
    50.  
    51. break;
    52.  
    53. }
    54.  
    55. }
    56.  
    57. // Didn't match. 给当前节点点打上Deletion标记
    58.  
    59. deleteRemainingChildren(returnFiber, child);
    60.  
    61. break;
    62.  
    63. } else {
    64.  
    65. // 2. key不相同, 匹配失败, 给当前节点打上Deletion标记
    66.  
    67. deleteChild(returnFiber, child);
    68.  
    69. }
    70.  
    71. child = child.sibling;
    72.  
    73. }
    74.  
    75. {
    76.  
    77. // ...省略部分代码, 只看核心逻辑
    78.  
    79. }
    80.  
    81. // 新建节点
    82.  
    83. const created = createFiberFromElement(element, returnFiber.mode, lanes);
    84.  
    85. created.ref = coerceRef(returnFiber, currentFirstChild, element);
    86.  
    87. created.return = returnFiber;
    88.  
    89. return created;
    90.  
    91. }
     

    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(
    3. returnFiber: Fiber,
    5. currentFirstChild: Fiber | null,
    7. newChild: any,
    9. lanes: Lanes,
    11. ): Fiber | null {
    12.  
    13. if (isArray(newChild)) {
    14.  
    15. return reconcileChildrenArray(
    16.  
    17. returnFiber,
    18.  
    19. currentFirstChild,
    20.  
    21. newChild,
    22.  
    23. lanes,
    24.  
    25. );
    26.  
    27. }
    28.  
    29. if (getIteratorFn(newChild)) {
    30.  
    31. return reconcileChildrenIterator(
    32.  
    33. returnFiber,
    34.  
    35. currentFirstChild,
    36.  
    37. newChild,
    38.  
    39. lanes,
    40.  
    41. );
    42.  
    43. }
    44.  
    45. }
     

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

     

    1. function reconcileChildrenArray(
    3. returnFiber: Fiber,
    5. currentFirstChild: Fiber | null,
    7. newChildren: Array<*>,
    9. lanes: Lanes,
    11. ): Fiber | null {
    12.  
    13. let resultingFirstChild: Fiber | null = null;
    14.  
    15. let previousNewFiber: Fiber | null = null;
    16.  
    17. let oldFiber = currentFirstChild;
    18.  
    19. let lastPlacedIndex = 0;
    20.  
    21. let newIdx = 0;
    22.  
    23. let nextOldFiber = null;
    24.  
    25. // 1. 第一次循环: 遍历最长公共序列(key相同), 公共序列的节点都视为可复用
    26.  
    27. for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
    28.  
    29. // 后文分析
    30.  
    31. }
    32.  
    33. if (newIdx === newChildren.length) {
    34.  
    35. // 如果newChildren序列被遍历完, 那么oldFiber序列中剩余节点都视为删除(打上Deletion标记)
    36.  
    37. deleteRemainingChildren(returnFiber, oldFiber);
    38.  
    39. return resultingFirstChild;
    40.  
    41. }
    42.  
    43. if (oldFiber === null) {
    44.  
    45. // 如果oldFiber序列被遍历完, 那么newChildren序列中剩余节点都视为新增(打上Placement标记)
    46.  
    47. for (; newIdx < newChildren.length; newIdx++) {
    48.  
    49. // 后文分析
    50.  
    51. }
    52.  
    53. return resultingFirstChild;
    54.  
    55. }
    56.  
    57. // ==================分割线==================
    58.  
    59. const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
    60.  
    61. // 2. 第二次循环: 遍历剩余非公共序列, 优先复用oldFiber序列中的节点
    62.  
    63. for (; newIdx < newChildren.length; newIdx++) {}
    64.  
    65. if (shouldTrackSideEffects) {
    66.  
    67. // newChildren已经遍历完, 那么oldFiber序列中剩余节点都视为删除(打上Deletion标记)
    68.  
    69. existingChildren.forEach(child => deleteChild(returnFiber, child));
    70.  
    71. }
    72.  
    73. return resultingFirstChild;
    74.  
    75. }
     

    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 个初始化序列:
     

     

     

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

     

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

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

     

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

     
 
    第一次循环
     

     

     

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

     
 
    第二次循环
     

     

     

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

    结果
     

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

    总结
     

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

                
  • 

                    相关阅读:
    
                    
Beyond Homophily: Structure-aware Path Aggregation Graph Neural Network                            
    
PS（Photoshop）去水印的4个方法                            
    
UVa129 Krypton Factor（困难的串）                            
    
分布式锁设计选型 不可重入锁建议使用ZooKeeper来实现 可重入锁建议使用Redis来实现 分布式锁：ZooKeeper不可重入锁 Java优化建议                            
    
MySQL中隐式转换的常见错误解决方法和技术                            
    
【机器学习】带你轻松理解什么是强化学习中的贝尔曼方程                            
    
项目之利用 V4L2应用程序框架 进行视频录制                            
    
关于VCTK数据集                            
    
【图像处理与机器视觉】图像处理概述与像素                            
    
数据结构 并查集                            
    
                        
                
    • 
                
  • 
                    原文地址：https://blog.csdn.net/weixin_44828588/article/details/126546481
                
    •