乐趣区

关于react.js:react-diff算法看这一篇再也不用害怕面试了

jiezi

react 源码解析 9.diff 算法

视频解说（高效学习）：进入学习

往期目录：

1. 开篇介绍和面试题

2.react 的设计理念

3.react 源码架构

4. 源码目录构造和调试

5.jsx& 外围 api

6.legacy 和 concurrent 模式入口函数

7.Fiber 架构

8.render 阶段

9.diff 算法

10.commit 阶段

11. 生命周期

12. 状态更新流程

13.hooks 源码

14. 手写 hooks

15.scheduler&Lane

16.concurrent 模式

17.context

18 事件零碎

19. 手写迷你版 react

20. 总结 & 第一章的面试题解答

在 render 阶段更新 Fiber 节点时，咱们会调用 reconcileChildFibers 比照 current Fiber 和 jsx 对象构建 workInProgress Fiber，这里 current Fiber 是指以后 dom 对应的 fiber 树，jsx 是 class 组件 render 办法或者函数组件的返回值。

在 reconcileChildFibers 中会依据 newChild 的类型来进入单节点的 diff 或者多节点 diff

//ReactChildFiber.old.js
function reconcileChildFibers(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChild: any,
): Fiber | null {

  const isObject = typeof newChild === 'object' && newChild !== null;

  if (isObject) {switch (newChild.$$typeof) {
      case REACT_ELEMENT_TYPE:
                // 繁多节点 diff
        return placeSingleChild(
            reconcileSingleElement(
              returnFiber,
              currentFirstChild,
              newChild,
              lanes,
            ),
          );
    }
  }
    //...
  
  if (isArray(newChild)) {
     // 多节点 diff
    return reconcileChildrenArray(
        returnFiber,
        currentFirstChild,
        newChild,
        lanes,
      );
  }

  // 删除节点
  return deleteRemainingChildren(returnFiber, currentFirstChild);
}

diff 过程的次要流程如下图：

咱们晓得比照两颗树的复杂度自身是 O(n3)，对咱们的利用来说这个是不能接受的量级，react 为了升高复杂度，提出了三个前提：

  1. 只对同级比拟，跨层级的 dom 不会进行复用
  2. 不同类型节点生成的 dom 树不同，此时会间接销毁老节点及子孙节点，并新建节点

  3. 能够通过 key 来对元素 diff 的过程提供复用的线索，例如：

    const a = (
    <>
      <p key="0">0</p>
      <p key="1">1</p>
    </>
  );
const b = (
  <>
    <p key="1">1</p>
    <p key="0">0</p>
  </>
);

​ 如果 a 和 b 里的元素都没有 key，因为节点的更新前后文本节点不同，导致他们都不能复用，所以会销毁之前的节点，并新建节点，然而当初有 key 了，b 中的节点会在老的 a 中寻找 key 雷同的节点尝试复用，最初发现只是替换地位就能够实现更新，具体比照过程前面会讲到。

单节点 diff

单点 diff 有如下几种状况：

  • key 和 type 雷同示意能够复用节点
  • key 不同间接标记删除节点，而后新建节点
  • key 雷同 type 不同，标记删除该节点和兄弟节点，而后新创建节点
function reconcileSingleElement(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  element: ReactElement
): Fiber {
  const key = element.key;
  let child = currentFirstChild;
  
  //child 节点不为 null 执行比照
  while (child !== null) {

    // 1. 比拟 key
    if (child.key === key) {

      // 2. 比拟 type

      switch (child.tag) {
        //...
        
        default: {if (child.elementType === element.type) {
            // type 雷同则能够复用 返回复用的节点
            return existing;
          }
          // type 不同跳出
          break;
        }
      }
      //key 雷同，type 不同则把 fiber 及和兄弟 fiber 标记删除
      deleteRemainingChildren(returnFiber, child);
      break;
    } else {
      //key 不同间接标记删除该节点
      deleteChild(returnFiber, child);
    }
    child = child.sibling;
  }
   
  // 新建新 Fiber
}

多节点 diff

多节点 diff 比较复杂，咱们分三种状况进行探讨，其中 a 示意更新前的节点，b 示意更新后的节点

  • 属性变动

    const a = (
    <>
      <p key="0" name='0'>0</p>
      <p key="1">1</p>
    </>
  );
  const b = (
    <>
      <p key="0" name='00'>0</p>
      <p key="1">1</p>
    </>
  );

  • type 变动

    const a = (
    <>
      <p key="0">0</p>
      <p key="1">1</p>
    </>
  );
  const b = (
    <>
      <div key="0">0</div>
      <p key="1">1</p>
    </>
  );

  • 新增节点

    const a = (
    <>
      <p key="0">0</p>
      <p key="1">1</p>
    </>
  );
  const b = (
    <>
      <p key="0">0</p>
      <p key="1">1</p>
      <p key="2">2</p>
    </>
  );

  • 节点删除

    const a = (
    <>
      <p key="0">0</p>
      <p key="1">1</p>
      <p key="2">2</p>
    </>
  );
  const b = (
    <>
      <p key="0">0</p>
      <p key="1">1</p>
    </>
  );

  • 节点地位变动

        const a = (
    <>
      <p key="0">0</p>
      <p key="1">1</p>
    </>
  );
  const b = (
    <>
      <p key="1">1</p>
      <p key="0">0</p>
    </>
  );

在源码中多节点 diff 有三个 for 循环遍历（并不意味着所有更新都有经验三个遍历，进入循环体有条件，也有条件跳出循环），第一个遍历解决节点的更新（包含 props 更新和 type 更新和删除），第二个遍历解决其余的状况（节点新增），其起因在于在大多数的利用中，节点更新的频率更加频繁，第三个解决位节点置扭转

  • 第一次遍历

    因为老的节点存在于 current Fiber 中，所以它是个链表构造，还记得 Fiber 双缓存构造嘛，节点通过 child、return、sibling 连贯，而 newChildren 存在于 jsx 当中，所以遍历比照的时候，首先让 newChildren[i]` 与 `oldFiber 比照，而后让 i ++、nextOldFiber = oldFiber.sibling。在第一轮遍历中，会解决三种状况，其中第 1，2 两种状况会完结第一次循环
    1. key 不同，第一次循环完结
    2. newChildren 或者 oldFiber 遍历完，第一次循环完结
    3. key 同 type 不同，标记 oldFiber 为 DELETION
    4. key 雷同 type 雷同则能够复用

    ​ newChildren 遍历完，oldFiber 没遍历完，在第一次遍历实现之后将 oldFiber 中没遍历完的节点标记为 DELETION，即删除的 DELETION Tag

  • 第二个遍历
    第二个遍历思考三种状况

    1. newChildren 和 oldFiber 都遍历完：多节点 diff 过程完结

      1. newChildren 没遍历完，oldFiber 遍历完，将剩下的 newChildren 的节点标记为 Placement，即插入的 Tag

        1. newChildren 和 oldFiber 没遍历完，则进入节点挪动的逻辑

  • 第三个遍历
    次要逻辑在 placeChild 函数中，例如更新前节点程序是 ABCD，更新后是 ACDB

    1. newChild 中第一个地位的 A 和 oldFiber 第一个地位的 A，key 雷同可复用，lastPlacedIndex=0

      1. newChild 中第二个地位的 C 和 oldFiber 第二个地位的 B，key 不同跳出第一次循环，将 oldFiber 中的 BCD 保留在 map 中
      1. newChild 中第二个地位的 C 在 oldFiber 中的 index=2 > lastPlacedIndex= 0 不须要挪动，lastPlacedIndex=2
      2. newChild 中第三个地位的 D 在 oldFiber 中的 index=3 > lastPlacedIndex= 2 不须要挪动，lastPlacedIndex=3
      3. newChild 中第四个地位的 B 在 oldFiber 中的 index=1 < lastPlacedIndex=3, 挪动到最初

    看图更直观

    例如更新前节点程序是 ABCD，更新后是 DABC

    1. newChild 中第一个地位的 D 和 oldFiber 第一个地位的 A，key 不雷同不可复用，将 oldFiber 中的 ABCD 保留在 map 中，lastPlacedIndex=0

      1. newChild 中第一个地位的 D 在 oldFiber 中的 index=3 > lastPlacedIndex= 0 不须要挪动，lastPlacedIndex=3
      1. newChild 中第二个地位的 A 在 oldFiber 中的 index=0 < lastPlacedIndex=3, 挪动到最初
      2. newChild 中第三个地位的 B 在 oldFiber 中的 index=1 < lastPlacedIndex=3, 挪动到最初
      3. newChild 中第四个地位的 C 在 oldFiber 中的 index=2 < lastPlacedIndex=3, 挪动到最初

    看图更直观

​ 代码如下：

//ReactChildFiber.old.js

function placeChild(newFiber, lastPlacedIndex, newIndex) {
       newFiber.index = newIndex;
   
       if (!shouldTrackSideEffects) {return lastPlacedIndex;}
   
    var current = newFiber.alternate;
 
       if (current !== null) {
         var oldIndex = current.index;
   
         if (oldIndex < lastPlacedIndex) {
           //oldIndex 小于 lastPlacedIndex 的地位 则将节点插入到最初
           newFiber.flags = Placement;
           return lastPlacedIndex;
         } else {return oldIndex;// 不须要挪动 lastPlacedIndex = oldIndex;}
       } else {
         // 新增插入
         newFiber.flags = Placement;
         return lastPlacedIndex;
       }
     }
//ReactChildFiber.old.js

function reconcileChildrenArray(
    returnFiber: Fiber,// 父 fiber 节点
    currentFirstChild: Fiber | null,//childs 中第一个节点
    newChildren: Array<*>,// 新节点数组 也就是 jsx 数组
    lanes: Lanes,//lane 相干 第 12 章介绍
  ): Fiber | null {

    let resultingFirstChild: Fiber | null = null;//diff 之后返回的第一个节点
    let previousNewFiber: Fiber | null = null;// 新节点中上次比照过的节点

    let oldFiber = currentFirstChild;// 正在比照的 oldFiber
    let lastPlacedIndex = 0;// 上次可复用的节点地位 或者 oldFiber 的地位
    let newIdx = 0;// 新节点中比照到了的地位
    let nextOldFiber = null;// 正在比照的 oldFiber
    for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {// 第一次遍历
      if (oldFiber.index > newIdx) {//nextOldFiber 赋值
        nextOldFiber = oldFiber;
        oldFiber = null;
      } else {nextOldFiber = oldFiber.sibling;}
      const newFiber = updateSlot(// 更新节点，如果 key 不同则 newFiber=null
        returnFiber,
        oldFiber,
        newChildren[newIdx],
        lanes,
      );
      if (newFiber === null) {if (oldFiber === null) {oldFiber = nextOldFiber;}
        break;// 跳出第一次遍历
      }
      if (shouldTrackSideEffects) {// 查看 shouldTrackSideEffects
        if (oldFiber && newFiber.alternate === null) {deleteChild(returnFiber, oldFiber);
        }
      }
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);// 标记节点插入
      if (previousNewFiber === null) {resultingFirstChild = newFiber;} else {previousNewFiber.sibling = newFiber;}
      previousNewFiber = newFiber;
      oldFiber = nextOldFiber;
    }

    if (newIdx === newChildren.length) {deleteRemainingChildren(returnFiber, oldFiber);// 将 oldFiber 中没遍历完的节点标记为 DELETION
      return resultingFirstChild;
    }

    if (oldFiber === null) {for (; newIdx < newChildren.length; newIdx++) {// 第 2 次遍历
        const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
        if (newFiber === null) {continue;}
        lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);// 插入新增节点
        if (previousNewFiber === null) {resultingFirstChild = newFiber;} else {previousNewFiber.sibling = newFiber;}
        previousNewFiber = newFiber;
      }
      return resultingFirstChild;
    }

    // 将剩下的 oldFiber 退出 map 中
    const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

    for (; newIdx < newChildren.length; newIdx++) {// 第三次循环 解决节点挪动
      const newFiber = updateFromMap(
        existingChildren,
        returnFiber,
        newIdx,
        newChildren[newIdx],
        lanes,
      );
      if (newFiber !== null) {if (shouldTrackSideEffects) {if (newFiber.alternate !== null) {
            existingChildren.delete(// 删除找到的节点
              newFiber.key === null ? newIdx : newFiber.key,
            );
          }
        }
        lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);// 标记为插入的逻辑
        if (previousNewFiber === null) {resultingFirstChild = newFiber;} else {previousNewFiber.sibling = newFiber;}
        previousNewFiber = newFiber;
      }
    }

    if (shouldTrackSideEffects) {
      // 删除 existingChildren 中剩下的节点
      existingChildren.forEach(child => deleteChild(returnFiber, child));
    }

    return resultingFirstChild;
  }
退出移动版