【React 18.2 源码学习】diff 算法包会——从手撸到源码

站长

2023年06月10日 15:19 · 阅读数 56

diff 过程入口

beginWork 会根据当前节点具体类型，进入对应的处理流程，在这些流程中最终都会执行 reconcileChildren， reconcileChildren 就是在 beginWork 中开始生成下一级 FiberNode 的入口函数，是协调（reconcile） 开始的地方，协调的过程也就是 React 中的 diff 过程。

【React 18.2 源码学习】diff 算法包会——从手撸到源码

可以看到初次渲染的时候执行了 mountChildFibers 方法，更新的时候执行了 reconcileChildFibers，但其实这两个方法是同一个方法，只是接收的参数不一样。接着看下两个方法的定义：

【React 18.2 源码学习】diff 算法包会——从手撸到源码

【React 18.2 源码学习】diff 算法包会——从手撸到源码可以看到这两方法都是执行 ChildReconciler 得来的，区别就是参数 shouldTrackSideEffects 一个为 true 一个为 false。shouldTrackSideEffects 的意思为是否在协调的时候标记副作用。

为什么初次渲染的时候 shouldTrackSideEffects 为 false 。

答案是为了初次渲染能有更好的性能。因为如果初次渲染也要标记副作用的话，会有很多的节点被标记为 Placement （新增节点），在 commit 阶段会依据副作用频繁操作 DOM （每个父 DOM 都会进行一次添加子 DOM 的操作），而不标记副作用时，因为根节点一直都存在，所以根节点是更新并会被标记 Placement，而其他节点会在 beginWork 阶段构建一棵离屏的 DOM 树，最终在 commit 阶段只需要根节点将 DOM 树一次性添加到页面即可。

reconcile（diff）算法解析

在 React 中，即使在最前沿的算法中，该算法的复杂程度为O(n3)，其中 n 是树中元素的数量。如果在 React 中使⽤了该算法，那么展示 1000 个元素所需要执⾏的计算量将在⼗亿的量级范围。这个开销实在是太过⾼昂。于是 React 基于以下三个条件将复杂度降低到了 O(n)。 1、只对同级元素进行 Diff。如果一个 DOM 元素更新前后跨越了层级，则不会复用。 2、两个不同类型的元素会产生不同的树。比如更新前是 p ，更新后是 div 则不会复用。 3、开发者可以通过 key prop 来暗示哪些⼦元素在不同的渲染下能保持稳定

在实践中发现以上条件在⼏乎所有实⽤的场景下都成立。下面从以下两种情况来看看 reconcile 算法具体是怎样的：

单节点 reconcile
多节点 reconcile

注意： 下面提到的老节点都是指的老的FiberNode，新节点指的是 React 元素（因为此时新节点还未生成Fiber，diff 的过程也是生成新节点对应的 FiberNode 的过程），不清楚 FiberNode 和 React 元素区别的可以看看我的JSX 竟然是 Fiber 的爷爷这篇文章

单节点 reconcile(diff)

下面是单节点 reconcile 的流程图。

【React 18.2 源码学习】diff 算法包会——从手撸到源码单节点 reconcile 是指新的节点只有一个，那为什么流程图中要进行遍历循环呢，这是因为虽然新的节点只有一个，但是之前的节点可能不止一个，所以要对老的节点进行循环，然后用遍历到的老节点和新的节点比较（同级比较）：

如果老节点和新节点的 key 相同，就继续判断 type ，如果也相同，那么这个节点就可以进行复用，然后返回这个复用的节点，并把其他节点标记为删除，然后结束当前的 reconcile 流程。
如果 type 不相同，则说明当前节点的类型发生了变化（比如从 p 变成了div），需要重新生成，剩下的节点全部标记删除，并结束当前的 reconcile 流程。（对应条件二）
如果老节点和新节点的 key 不相同，标记老节点删除，继续遍历。
如果遍历结束也没有找到和新节点 key 相同的老节点，那么就会重新生成节点，结束当前的 reconcile 流程。

下面手撸一个丐版单节点 diff

function cloneFiber(old, new){
    return {
        ...oldFiber,
        ...newFiber
    }
}
  function Fiber(old, new){
    return {...new }
}
function reconcileSingleElement(oldArr, newChild) {
    const result = null;
    for(let i =0; i < oldArr.length; i++) {
        const oldchild = oldArr[i];
        if(oldchild.key === newChild.key) {
            if(oldchild.key === newChild.key) {
                // 复用    
                result = cloneFiber(oldchild,newchild)
            }else {
                //不能复用删除剩下的节点并 跳出循环
                break
            }
        }
    }
    // 新生成节点
    result = new Fiber(newChild);
    return result
}

多节点 reconcile(diff)

多节点的情况比单节点要复杂的多，主要分为以下几个情况：

节点不变（可能节点内容会存在更新）
节点增加或者删除
节点移动

那针对上面的情况，diff 的算法设计思路是：

判断当前节点属于哪种情况
如果是增删，执行增删逻辑
如果位置不变，执行相应更新逻辑
如果是移动，执行移动逻辑因为在日常开发中，‘节点移动’的情况会比较少（反正我目前还没咋遇到过），因此在优先级相同的情况下， diff 算法会优先处理另外两个情况。基于以上信息，diff 算法会经历两轮遍历：

第一轮尝试尽可能的按顺序复用节点
第二轮遍历处理剩下的节点。当然也有例外，对于位置不变的情况下，只需要进行第一轮遍历。下面是多节点的流程图

第一轮遍历

首先来看第一轮遍历，当新老节点 key 不相同的跳出第一轮循环，当新老节点key相同时继续循环，分为两种情况，一种是新老节点 type 相同，此时节点可以复用。另一种情况是 type 不同，此时节点不能复用，需要生成新的节点同时给老节点标记删除。不管 type 是否相同都会更新最后一个被复用节点的索引（这个索引被用来判断节点是否发生移动）。如果正常循环退出时，老节点和新节点都遍历完成，则不需要进入第二轮遍历，diff 结束。

第二轮遍历

第二轮遍历分为几种情况：第一种新节点在第一轮遍历完了，旧节点没遍历完，新少旧多说明有删除的节点，第二轮遍历需要删除剩余的老节点。第二种是新节点没遍历完，但是旧节点遍历完了，旧少新多说明有新增的节点，第二轮遍历需要创建新节点并打上新增的标记

第三种是新老节点都没遍历完，说明发生了移动，第二轮遍历需要处理移动。为了查找的效率，需要将老节点以 key 为索引存在 map 中，通过遍历新节点同时根据新节点的 key 找出可以复用的老节点，如果找到则把 map 中对应的老节点删除，然后根据最后一个被复用的节点的位置确定当前节点是否移动。遍历结束后将 map 中的节点全部标记删除

如何判断节点移动

根据 lastPlacedIndex （最后一个可复用的节点的位置索引，这个对应的是老节点的位置索引）来判断。因为新节点中的节点顺序代表了更新后的节点顺序，如果新节点能找到相同 key 对应的老节点，那么会有两种情况： 1、oldFiber.index < lastPlacedIndex 说明 oldFIber 在 lastPlacedIndex 对应的老节点左边，也就是原来这个节点在 lastPlacedIndex 对应节点的左边，但是当前的新节点一定在 lastPlacedIndex 对应的新节点的右边（因为新节点的顺序就是更新后的节点顺序，因此后遍历的节点会在先遍历的节点的右边），因此当前的新 FIberNode 发生了移动 2、oldFiber.index >= lastPlacedIndex 说明 oldFIber 在 lastPlacedIndex 对应的节点右边，与新节点当前位置一致，所以没有发生移动，同时更新 lastPlacedIndex 的值为 oldFiber.index

举个例子

【React 18.2 源码学习】diff 算法包会——从手撸到源码

需要注意的是，在开发中要尽量避免将后面的节点移动到前面，因为这会导致性能不好，可以看下面的例子【React 18.2 源码学习】diff 算法包会——从手撸到源码

手撸多节点 diff

下面我们来利用上面的策略实现一个丐版的 diff 算法：主要功能是 diff 两个数组对象，并标记出新旧数组对象的变化；

   /*
   入参：[]{
              key:1,
              type: 'div'
          },
   */
    function cloneFiber(old, new){
        return {
            ...oldFiber,
            ...newFiber
        }
    }
   function Fiber(old, new){
       return {...new }
   }
    function reconcileArray(
        oldArray,
        newArray,
      ){
        // diff 结果存放数组
        const resultArr = [];
        // 最后一个复用的位置
        let lastPlacedIndex = 0;
        // 遍历新数组对象的索引
        let newIdx = 0;
        // 遍历旧数组对象的索引
        let oldIdx = 0;
        
        // 第一轮遍历
        for (; oldIdx < oldArray.length && newIdx < newArray.length; newIdx++, oldIdx++) {
          const oldItem = oldArray[oldIdx];
          const newItem = newArray[newIdx];

          let resultItem = null;
          if(oldItem.key === newItem.key) {
              if(oldItem.type === newItem.type) {
                // key 和 type 都相同  复用
                resultItem = cloneFiber(oldItem, newItem);
              } else {
                // key 相同，type 不相同生成一个新的节点
                resultItem = new Fiber(newItem);
                // 原来的节点删除
                oldItem.flag = 'Deletion';
                resultArr.push(oldItem);
              }
          } else {
            // key 不相同跳出第一轮循环
            break;
          }
          // 更新最后一个复用的位置，并标记对应的副作用
          lastPlacedIndex = placeChild(oldArray, newItem, lastPlacedIndex);
          
          resultArr.push(newItem)
        }

        if (newIdx === newArray.length) {
          // 说明新节点已经遍历完了，需要给剩下的老节点标记删除
          for(; oldIdx < oldArray.length; oldIdx++) {
            const oldItem = oldArray[oldIdx]
            oldItem.flag = 'Deletion';
            resultArr.push(oldItem);
          } 
          // diff结束
          return resultArr;
        }

        if (oldIdx === oldArray.length) {
          // 旧节点已经全部遍历完了，新节点还有，对剩下的新节点标记更新
          for(; newIdx < newArray.length; newIdx++) {
            const newItem = newArray[newIdx]
            newItem.flag = 'Placement';
            resultArr.push(newItem);
          } 
          // diff 结束
          return resultArr;
        }

        // 将剩下的老节点用key值存储到 map 中方便快速查找 
        const existingChildren = mapRemainingChildren(oldArray, oldIdx);

        // 对剩下的新节点进行遍历，并对老节点尽可能的复用
        for (; newIdx < newArray.length; newIdx++) {
          const newItem = newArray[newIdx];
          // 根据 key 获取对应的老节点
          const oldItem = existingChildren.get(newItem.key || newIdx);
          let resultItem = null;
          if(oldItem) {
              // 找到了对应的老节点
            if(oldItem.key === newItem.key) {
                if(oldItem.type === newItem.type) {
                  // key 和 type 都相同  复用
                  resultItem = cloneFiber(oldItem, newItem);
                } else {
                  // key 相同，type 不相同生成一个新的节点
                  resultItem =  new Fiber(newItem);
                  // 原来的节点删除
                  oldItem.flag = 'Deletion';
                  resultArr.push(oldItem);
                }
            } 
            // 将 map 中对应的老节点删除
            existingChildren.delete(newItem.key || newIdx);
          } else{
             // 没找到对应的老节点 生成新节点
             resultItem = {...newItem};
          }
          // 更新最后一个复用的位置，并标记对应的副作用
          lastPlacedIndex = placeChild(oldArray, resultItem, lastPlacedIndex);
          resultArr.push(resultItem);
        }

        // 将 map 中剩下的节点都标记为删除
        existingChildren.forEach(item => {
            item.flag = 'Deletion';
            resultArr.push(item);
        });

        return resultArr;
      }

      function placeChild(oldArray, newItem,lastPlacedIndex) {
        // 这里是替代 react 中取老节点的index
        const oldIdx = oldArray.findIndex(item => newItem.key === item.key);
        if(oldIdx < 0) {
            // 没有找到对应的老节点,说明是新增
            newItem.flag = 'Placement';
        } else {
            // 找到了老节点
            if(oldIdx < lastPlacedIndex) {
                // 说明移动了
                newItem.flag = 'Placement-Move';
                return lastPlacedIndex
            } else {
                // 没有移动,同时更新最后复用的位置
                return oldIdx
            }
        }
      }

      function mapRemainingChildren(oldArr, index) {
        const map = new Map();
        for(let i = index; i < oldArr.length; i++) {
            const item = oldArr[i];
            if(item.key) {
                // key 存在
                map.set(item.key, item);
            } else {
                // key 不存在 用 index 替代 key 值
                map.set(index, item)
            }   
        }
        return map;
      }

      const old = [
          {
              key:1,
              type: 'div'
          },
          {
            key:2,
            type: 'div'
        },
        {
            key:3,
            type: 'div'
        },
        {
            key:4,
            type: 'div'
        },
        {
            key:5,
            type: 'div'
        },
      ]

      const newArr = [
        {
            key:5,
            type: 'div'
        },
        {
            key:1,
            type: 'div'
        },
        {
          key:2,
          type: 'div'
      },
      {
          key:3,
          type: 'div'
      },
      {
          key:6,
          type: 'div'
      },
    ]

    const result = reconcileArray(old,newArr);
    console.log(result);