react diff 学习

基于Fiber的React Diff算法源码分析_Fiber_贝壳大前端技术团队_InfoQ写作平台

一、简介React15整体架构分为两层：Reconciler（协调器）层和Renderer（渲染器）层，Reconciler负责找出变化的组件，Renderer负责将变化的组件渲染到页面上，其中，Re

https://xie.infoq.cn/article/9771629d41f19743a08a1d481

双缓存Fiber树

在React中最多会同时存在两棵Fiber树。当前屏幕上显示内容对应的Fiber树称为current Fiber树，正在内存中构建的Fiber树称为workInProgress Fiber树。

current Fiber树中的Fiber节点被称为current fiber，workInProgress Fiber树中的Fiber节点被称为workInProgress fiber，他们通过alternate属性连接。


currentFiber.alternate === workInProgressFiber;
workInProgressFiber.alternate === currentFiber;

首次执行ReactDOM.render会创建rootFiberNode和rootFiber。其中rootFiberNode是整个应用的根节点，rootFiber是<App/>所在组件树的根节点。

rootFiberNode的current会指向当前页面上已渲染内容对应对Fiber树，被称为current Fiber树。

接下来进入render阶段，根据组件返回的JSX在内存中依次创建Fiber节点并连接在一起构建Fiber树，被称为workInProgress Fiber树。（下图中右侧为内存中构建的树，左侧为页面显示的树）

在构建workInProgress Fiber树时会尝试复用current Fiber树中已有的Fiber节点内的属性，在首屏渲染时只有rootFiber存在对应的current fiber（即rootFiber.alternate）。

图中右侧已构建完的workInProgress Fiber树在commit阶段渲染到页面。

此时DOM更新为右侧树对应的样子。rootFiberNode的current指针指向workInProgress Fiber树使其变为current Fiber 树。

update时

接下来我们点击p节点触发状态改变，这会开启一次新的render阶段并构建一棵新的workInProgress Fiber 树。

workInProgress Fiber 树在render阶段完成构建后进入commit阶段渲染到页面上。渲染完毕后，workInProgress Fiber 树变为current Fiber 树。

Diff

前后两棵树完全比对的算法的复杂程度为 O(n 3 )，其中n是树中元素的数量。

为了降低算法复杂度，React的diff会预设三个限制：

只对同级元素进行Diff。如果一个DOM节点在前后两次更新中跨越了层级，那么React不会尝试复用他。

两个不同类型的元素会产生出不同的树。如果元素由div变为p，React会销毁div及其子孙节点，并新建p及其子孙节点。

开发者可以通过 key prop来暗示哪些子元素在不同的渲染下能保持稳定。


// 根据newChild类型选择不同diff函数处理
function reconcileChildFibers(
 returnFiber: Fiber, //父节点 新生成的第一个fiber的return会被指向它
    currentFirstChild: Fiber | null, //旧fiber节点，diff生成新fiber节点时会用新生成的ReactElement和它作比较。
    newChild: any //新生成的ReactElement，会以它为标准生成新的fiber节点,
    lanes: Lanes //本次的渲染优先级，最终会被挂载到新fiber的lanes属性上,
): Fiber | null {

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

  if (isObject) {
    // object类型，可能是 REACT_ELEMENT_TYPE 或 REACT_PORTAL_TYPE
    switch (newChild.$$typeof) {
      case REACT_ELEMENT_TYPE:
        // 调用 reconcileSingleElement 处理
      // // ...省略其他case
    }
  }

  if (typeof newChild === 'string' || typeof newChild === 'number') {
    // 调用 reconcileSingleTextNode 处理
    // ...省略
  }

  if (isArray(newChild)) {
    // 调用 reconcileChildrenArray 处理
    // ...省略
  }

  // 一些其他情况调用处理函数
  // ...省略

  // 以上都没有命中，删除节点
  return deleteRemainingChildren(returnFiber, currentFirstChild);
}


<div key="a">aa</div>


{
   $$typeof: Symbol(react.element), type: "div", key: "a" 
   ...
}

单个节点，会进入reconcileSingleElement


function reconcileSingleElement(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  element: ReactElement
): Fiber {
  const key = element.key;
  let child = currentFirstChild;

  // 首先判断是否存在对应DOM节点
  while (child !== null) {
    // 上一次更新存在DOM节点，接下来判断是否可复用

    // 首先比较key是否相同
    if (child.key === key) {

      // key相同，接下来比较type是否相同

      switch (child.tag) {
        // ...省略case

        default: {
          if (child.elementType === element.type) {
            // type相同则表示可以复用
            // 返回复用的fiber
            return existing;
          }

          // type不同则跳出循环
          break;
        }
      }
      // 代码执行到这里代表：key相同但是type不同
      // 将该fiber及其兄弟fiber标记为删除
      deleteRemainingChildren(returnFiber, child);
      break;
    } else {
      // key不同，将该fiber标记为删除
      deleteChild(returnFiber, child);
    }
    child = child.sibling;
  }

  // 创建新Fiber，并返回 ...省略
}

React通过先判断key是否相同，如果key相同则判断type是否相同，只有都相同时一个DOM节点才能复用。

当child !== null且key相同且type不同时执行deleteRemainingChildren将child及其兄弟fiber都标记删除。

当child !== null且key不同时仅将child标记删除。


// 更新前
<div>ka song</div>
// 更新后
<p>ka song</p>

// 未设置key prop默认 key = null;，所以更新前后key相同，都为null，但是更新前type为div，更新后为p，type改变则不能复用
-----------------------------

// 更新前
<div key="xxx">ka song</div>
// 更新后
<div key="ooo">ka song</div>

// 更新前后key改变，不需要再判断type，不能复用。
-----------------------------

// 更新前
<div key="xxx">ka song</div>
// 更新后
<p key="ooo">ka song</p>

//更新前后key改变，不需要再判断type，不能复用。
-----------------------------

// 更新前
<div key="xxx">ka song</div>
// 更新后
<div key="xxx">xiao bei</div>

// 更新前后key与type都未改变，可以复用。children变化，DOM的子元素需要更新。
-----------------------------

多点diff


function List () {
  return (
    <ul>
      <li key="0">0</li>
      <li key="1">1</li>
      <li key="2">2</li>
      <li key="3">3</li>
    </ul>)
}


{
  $$typeof: Symbol(react.element),
  key: null,
  props: {
    children: [
      {$$typeof: Symbol(react.element), type: "li", key: "0", ref: null, props: {…}, …}
      {$$typeof: Symbol(react.element), type: "li", key: "1", ref: null, props: {…}, …}
      {$$typeof: Symbol(react.element), type: "li", key: "2", ref: null, props: {…}, …}
      {$$typeof: Symbol(react.element), type: "li", key: "3", ref: null, props: {…}, …}
    ]
  },
  ref: null,
  type: "ul"
}

reconcileChildFibers的newChild参数类型为Array


// 节点更新
<ul>
  <li key="0" className="before">0<li>
  <li key="1">1<li>
</ul>

// 节点属性变化
<ul>
  <li key="0" className="after">0<li>
  <li key="1">1<li>
</ul>

// 节点类型更新
<ul>
  <div key="0">0<li>
  <li key="1">1<li>
</ul>

-----------------------------------------
// 节点新增或减少
<ul>
  <li key="0">0<li>
  <li key="1">1<li>
</ul>

// 新增节点
<ul>
  <li key="0">0<li>
  <li key="1">1<li>
  <li key="2">2<li>
</ul>

// 删除节点
<ul>
  <li key="1">1<li>
</ul>

-----------------------------------------
// 节点位置变化
<ul>
  <li key="0">0<li>
  <li key="1">1<li>
</ul>

<ul>
  <li key="1">1<li>
  <li key="0">0<li>
</ul>

在日常开发中，相较于新增和删除，更新组件发生的频率更高。所以Diff 会优先判断当前节点是否属于更新。

第一轮遍历：处理更新的节点。

第二轮遍历：处理剩下的不属于更新的节点。


		let oldFiber = currentFirstChild;
    let lastPlacedIndex = 0;
    let newIdx = 0;
    let nextOldFiber = null;
    for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
      if (oldFiber.index > newIdx) {
        nextOldFiber = oldFiber;
        oldFiber = null;
      } else {
        nextOldFiber = oldFiber.sibling;
      }
      const newFiber = updateSlot(
        returnFiber,
        oldFiber,
        newChildren[newIdx],
        lanes,
      );
      if (newFiber === null) {
        // TODO: This breaks on empty slots like null children. That's
        // unfortunate because it triggers the slow path all the time. We need
        // a better way to communicate whether this was a miss or null,
        // boolean, undefined, etc.
        if (oldFiber === null) {
          oldFiber = nextOldFiber;
        }
        break;
      }
      if (shouldTrackSideEffects) {
        if (oldFiber && newFiber.alternate === null) {
          // We matched the slot, but we didn't reuse the existing fiber, so we
          // need to delete the existing child.
          deleteChild(returnFiber, oldFiber);
        }
      }
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      if (previousNewFiber === null) {
        // TODO: Move out of the loop. This only happens for the first run.
        resultingFirstChild = newFiber;
      } else {
        // TODO: Defer siblings if we're not at the right index for this slot.
        // I.e. if we had null values before, then we want to defer this
        // for each null value. However, we also don't want to call updateSlot
        // with the previous one.
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
      oldFiber = nextOldFiber;
    }

第一轮遍历：

let newIds = 0，遍历newChildren，将newChildren[i]与oldFiber比较，判断DOM节点是否可复用。

如果可复用，newIds++，继续比较newChildren[i]与oldFiber.sibling，可以复用则继续遍历。

如果不可复用，立即跳出整个遍历，第一轮遍历结束。


// 之前
<li key="0">0</li>
<li key="1">1</li>
<li key="2">2</li>
            
// 之后
<li key="0">0</li>
<li key="1">1</li>
<div key="2">2</div>
<li key="3">3</li>

如果newChildren遍历完（即newIds === newChildren.length - 1）或者oldFiber遍历完（即oldFiber.sibling === null），跳出遍历，第一轮遍历结束。


// 之前
<li key="0" className="a">0</li>
<li key="1" className="b">1</li>
            
// 之后 情况1 —— newChildren与oldFiber都遍历完
<li key="0" className="aa">0</li>
<li key="1" className="bb">1</li>
            
// 之后 情况2 —— newChildren没遍历完，oldFiber遍历完
// newChildren剩下 key==="2" 未遍历
<li key="0" className="aa">0</li>
<li key="1" className="bb">1</li>
<li key="2" className="cc">2</li>
            
// 之后 情况3 —— newChildren遍历完，oldFiber没遍历完
// oldFiber剩下 key==="1" 未遍历
<li key="0" className="aa">0</li>

第二轮遍历

`newChildren`与`oldFiber`同时遍历完

那就是最理想的情况：只有组件更新。此时Diff结束。

`newChildren`没遍历完，`oldFiber`遍历完

已有的DOM节点都复用了，这时还有新加入的节点，意味着本次更新有新节点插入，我们只需要遍历剩下的newChildren为生成的workInProgress fiber依次标记Placement。


if (oldFiber === null) {
      // If we don't have any more existing children we can choose a fast path
      // since the rest will all be insertions.
      for (; newIdx < newChildren.length; newIdx++) {
        const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
        if (newFiber === null) {
          continue;
        }
        lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
        if (previousNewFiber === null) {
          // TODO: Move out of the loop. This only happens for the first run.
          resultingFirstChild = newFiber;
        } else {
          previousNewFiber.sibling = newFiber;
        }
        previousNewFiber = newFiber;
      }
      return resultingFirstChild;
    }

`newChildren`遍历完，`oldFiber`没遍历完

意味着本次更新比之前的节点数量少，有节点被删除了。所以需要遍历剩下的oldFiber，依次标记Deletion。


if (newIdx === newChildren.length) {
      // We've reached the end of the new children. We can delete the rest.
      deleteRemainingChildren(returnFiber, oldFiber);
      return resultingFirstChild;
    }

`newChildren`与`oldFiber`都没遍历完

这意味着有节点在这次更新中改变了位置


// Add all children to a key map for quick lookups.
    const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

// Keep scanning and use the map to restore deleted items as moves.
    for (; newIdx < newChildren.length; newIdx++) {
      const newFiber = updateFromMap(
        existingChildren,
        returnFiber,
        newIdx,
        newChildren[newIdx],
        lanes,
      );
      if (newFiber !== null) {
        if (shouldTrackSideEffects) {
          if (newFiber.alternate !== null) {
            // The new fiber is a work in progress, but if there exists a
            // current, that means that we reused the fiber. We need to delete
            // it from the child list so that we don't add it to the deletion
            // list.
            existingChildren.delete(
              newFiber.key === null ? newIdx : newFiber.key,
            );
          }
        }
        lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
        if (previousNewFiber === null) {
          resultingFirstChild = newFiber;
        } else {
          previousNewFiber.sibling = newFiber;
        }
        previousNewFiber = newFiber;
      }
    }

由于有节点改变了位置，所以不能再用位置索引newIdx对比前后的节点，那么如何才能将同一个节点在两次更新中对应上呢？

我们需要使用key。

为了快速的找到key对应的oldFiber，我们将所有还未处理的oldFiber存入以key为key，oldFiber为value的Map中

接下来遍历剩余的newChildren，通过newChildren[i].key就能在existingChildren中找到key相同的oldFiber。

既然我们的目标是寻找移动的节点，那么我们需要明确：节点是否移动是以什么为参照物？

我们的参照物是：最后一个可复用的节点在oldFiber中的位置索引（用变量lastPlacedIndex表示）。

由于本次更新中节点是按newChildren的顺序排列。在遍历newChildren过程中，每个遍历到的可复用节点一定是当前遍历到的所有可复用节点中最靠右的那个，即一定在lastPlacedIndex对应的可复用的节点在本次更新中位置的后面。

那么我们只需要比较遍历到的可复用节点在上次更新时是否也在lastPlacedIndex对应的oldFiber后面，就能知道两次更新中这两个节点的相对位置改变没有。

我们用变量oldIndex表示遍历到的可复用节点在oldFiber中的位置索引。如果oldIndex < lastPlacedIndex，代表本次更新该节点需要向右移动。

lastPlacedIndex初始为0，每遍历一个可复用的节点，如果oldFiber >= lastPlacedIndex，则lastPlacedIndex = oldFiber。

Demo

每个字母代表一个节点，字母的值代表节点的key


// 之前
abcd

// 之后
acdb

===第一轮遍历开始===
a（之后）vs a（之前）
key不变，可复用
此时 a 对应的oldFiber（之前的a）在之前的数组（abcd）中索引为0
所以 lastPlacedIndex = 0;

继续第一轮遍历...

c（之后）vs b（之前）
key改变，不能复用，跳出第一轮遍历
此时 lastPlacedIndex === 0;
===第一轮遍历结束===

===第二轮遍历开始===
newChildren === cdb，没用完，不需要执行删除旧节点
oldFiber === bcd，没用完，不需要执行插入新节点

将剩余oldFiber（bcd）保存为map

// 当前oldFiber：bcd
// 当前newChildren：cdb

继续遍历剩余newChildren

key === c 在 oldFiber中存在
const oldIndex = c（之前）.index;
此时 oldIndex === 2;  // 之前节点为 abcd，所以c.index === 2
比较 oldIndex 与 lastPlacedIndex;

如果 oldIndex >= lastPlacedIndex 代表该可复用节点不需要移动
并将 lastPlacedIndex = oldIndex;
如果 oldIndex < lastplacedIndex 该可复用节点之前插入的位置索引小于这次更新需要插入的位置索引，代表该节点需要向右移动

在例子中，oldIndex 2 > lastPlacedIndex 0，
则 lastPlacedIndex = 2;
c节点位置不变

继续遍历剩余newChildren

// 当前oldFiber：bd
// 当前newChildren：db

key === d 在 oldFiber中存在
const oldIndex = d（之前）.index;
oldIndex 3 > lastPlacedIndex 2 // 之前节点为 abcd，所以d.index === 3
则 lastPlacedIndex = 3;
d节点位置不变

继续遍历剩余newChildren

// 当前oldFiber：b
// 当前newChildren：b

key === b 在 oldFiber中存在
const oldIndex = b（之前）.index;
oldIndex 1 < lastPlacedIndex 3 // 之前节点为 abcd，所以b.index === 1
则 b节点需要向右移动
===第二轮遍历结束===

最终acd 3个节点都没有移动，b节点被标记为移动

补充

根据同级的节点数量将 Diff 算法分为两类，单节点 Diff 和多节点 Diff：

当 newChild 类型为 object、number、string，代表同级只有一个节点，会调用单节点 Diff 函数 reconcileSingleElement 函数。

当 newChild 类型为 Array，表示同级有多个节点，会调用多节点 Diff 函数 reconcileChildrenArray 函数。


function reconcileChildFibers(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChild: any,
): Fiber | null {
  const isObject = typeof newChild === 'object' && newChild !== null;
  if (isObject) {
      // object类型，可能是 REACT_ELEMENT_TYPE 或 REACT_PORTAL_TYPE
      switch (newChild.$typeof) {
          case REACT_ELEMENT_TYPE:
          // 调用 reconcileSingleElement 处理
          // ...其他case
      }
  }
  if (typeof newChild === 'string' || typeof newChild === 'number') 
  {
      // 调用 reconcileSingleTextNode 处理
  }
  if (isArray(newChild)) {
      // 调用 reconcileChildrenArray 处理
  }
  // 以上都没有命中，删除节点
  return deleteRemainingChildren(returnFiber, currentFirstChild);
}

首先是单点diff


function reconcileSingleElement(
    returnFiber: Fiber,   
    currentFirstChild: Fiber | null,
    element: ReactElement
): Fiber {
  const key = element.key;
  let child = currentFirstChild;
  // 首先判断是否存在对应DOM节点
  while (child !== null) {
      // 上一次更新存在DOM节点，接下来判断是否可复用
      // 首先比较key是否相同
      if (child.key === key) {
      // key相同，接下来比较type是否相同
      switch (child.tag) {
          // ...省略case
          default: {
          if (child.elementType === element.type) {
              // type相同则表示可以复用
              // 返回复用的fiber
              return existing;
          }
          // type不同则跳出switch
          break;
          }
      }
      // 不能复用的节点，被标记为删除
      deleteRemainingChildren(returnFiber, child);
      break;
      } else {
          // key不同，将该fiber标记为删除
          deleteChild(returnFiber, child);
      }
      child = child.sibling;
  }
  // 创建新Fiber，并返回 ...省略
}

多节点 Diff

对于同级有多个元素的节点，Diff 算法要处理的情况相对复杂，但可以总结归纳为三种情况，第一种为节点新增或减少，第二种为节点更新，第三种为节点位置发生变化。

多节点 Diff 第一轮遍历

第一轮遍历的目的是处理更新节点，处理流程图如图所示，其中的 newChildren 为被转译后的 JSX 对象，orderFiber 为链表结构的 current Fiber 树。


// 更新之前
<div key="id1" className="a">1</div>
<div key="id2" className="b">2</div>
// 更新之后情况1 newChildren与oldFiber都遍历完
<div key="id1" className="aa">1</div>
<div key="id2" className="bb">2</div>
// 更新之后情况2 newChildren没遍历完，oldFiber遍历完
<div key="id1" className="aa">1</div>
<div key="id2" className="bb">2</div>
<div key="id3" className="cc">3</div>
// 更新之后情况3 newChildren遍历完，oldFiber没遍历完
<div key="id1" className="aa">1</div>

结果一：可能 newChildren 遍历完，或 oldFiber 遍历完，或他们同时遍历完。

newChildren 与 oldFiber 同时遍历完，如更新之后情况 1。

这是最理想的情况，只需在第一轮遍历进行组件更新，此时 Diff 结束。

newChildren 没遍历完，oldFiber 遍历完，如更新之后情况 2。

因为 oldFiber 树遍历完，所以已有的 DOM 节点都复用了，同时 newChildren 没遍历完，表示有新加入的节点，我们只需要遍历剩下的 newChildren，并生成新的 workInProgress fiber 节点，依次标记 Placement，此时 Diff 结束。

newChildren 遍历完，oldFiber 没遍历完，如更新之后情况 3。

newChildren 遍历完，同时 oldFiber 没遍历完，意味着更新之后的节点比更新之前的节点数量少了，即有节点被删除了。所以需要遍历剩下的 oldFiber，依次剩余的 olderFiber 节点标记 Deletion，此时 Diff 结束。

结果二：因为 key 不同跳出的遍历，表示此时的 newChildren 没有遍历完，oldFiber 也没有遍历完。

例如


//更新之前
<div key="id1">1</div>
<div key="id2">2</div>
<div key="id3">3</div>

//更新之后
<div key="id1">1</div>
<div key="id3">3</div>
<div key="id2">2</div>

newChildren 与 oldFiber 都没遍历完，这意味着有节点在这次更新中改变了位置，需要进行第二轮遍历。

多节点 Diff 第二轮遍历

因为第二轮遍历需要处理改变位置的节点，所以为了方便找到拥有同一个 key 的 newChildren 和 olderFiber 节点，react 将所有还未处理的 oldFiber 存入以 key 为 key，oldFiber 为 value 的 Map 中。


const existingChildren = mapRemainingChildren(returnFiber,oldFiber)

接下来遍历剩余的 newChildren，通过 newChildren[i].key 就能很快在 existingChildren 中找到 key 相同的 oldFiber 节点。

因为有节点的位置发生了移动，所以需要选一个参照的节点，来判断其他的节点是否移动，React 选定最后一个可复用的节点为参照物，记下其在 oldFiber 中的位置索引，用变量 lastPlacedIndex 表示。

由于更新中节点是按 newChildren 的顺序排列，所以在遍历 newChildren 过程中，每个遍历到的可复用节点一定是当前遍历到的所有可复用节点中最靠右的那个。

用变量 oldIndex 表示遍历到的可复用节点在 oldFiber 中的位置索引，如果 oldIndex < lastPlacedIndex，代表本次更新该节点需要被移动（标记为 Placement），oldIndex > lastPlacedIndex 代表该节点不需要被移动。

其中，lastPlacedIndex 初始为 0，更新 lastPlacedIndex 规则为：每遍历一个可复用的节点，如果 oldIndex >= lastPlacedIndex，则更新 lastPlacedIndex 为 oldIndex，否则，不更新。

下面通过一个例子阐述下整个 Diff 过程，为了简化 Diff 过程，其中的 ABCD 表示 DOM 树的节点，字母的值表示节点的 key。

如上图所示，app 节点下有顺序为 ABCD 四个节点，若将 app 节点下变为 ADBE，Diff 算法会经历下面的过程。

1)第一轮遍历

第一轮遍历 newChildren 开始，节点 A 可复用，此时的 workInProgress Fiber 树为

继续遍历下一个节点，因 newChildren 第二个节点 D 和 oldFiber 中下一个节点 B 的 key 不相同跳出第一轮遍历，进行第二轮遍历。

第二轮遍历

此时的 olderFiber 和 newChildren 如下：

此时 lastPlacedIndex 为 0，Map 为{B:B，C:C，D:D}，接下来继续遍历 newChildren 的下一个节点为 D，key 为 D 的节点在 Map 中存在，D 节点的 oldIndex 为 3，oldIndex > lastPlacedIndex，D 节点可以复用，位置也不需要移动。

此时的 workInProgress Fiber 树为：

更新 lastPlacedIndex 为 3，此时 Map 为{B:B，C:C}，继续遍历 newChildren 下一个节点 B，key 为 B 的节点在 Map 中存在，B 节点的 oldIndex 为 1，oldIndex < lastPlacedIndex，所以 B 节点可复用，但是需要移动，所以为 B 节点打上 Placement 标签。

此时的 workInProgress Fiber 树为：