写点什么

基于 Fiber 的 React Diff 算法源码分析

  • 2021 年 11 月 11 日
  • 本文字数:8568 字

    阅读完需:约 28 分钟

基于Fiber的React Diff算法源码分析

一、简介

  React15 整体架构分为两层:Reconciler(协调器)层和 Renderer(渲染器)层,Reconciler 负责找出变化的组件,Renderer 负责将变化的组件渲染到页面上,其中,Reconciler 采用递归的方式创建虚拟 DOM,由于递归过程是不能中断的,如果组件树的层级很深,递归会占用线程很多时间,会造成页面卡顿。

  为了解决这个问题,React 团队决定重写整个架构,基于全新的 Fiber 架构将无法中断的递归更新重构为异步的可中断更新,于是,Fiber 搭载 React16 版本的顺风车跟大家见面了。

  我们都知道 Diff 算法是为了找出变化的元素,作为 Reconciler 层重要一环,扮演着重要的角色。本文从源码角度就全新的 React Fiber 架构和大家聊一聊 Diff 算法,包含以下三个部分:

  • React 15 和 React 16 版本的对比

  • Fiber 是什么,以及 Fiber 节点如何连接成 Fiber 树

  • 从源码角度介绍下 Diff 算法的整个过程

二、React15 Vs React16

  React15 将整体架构分为了两层,如图一所示,react16 将整体架构分为了三层,如图二所示:


图一 React15整体架构


图二 React16整体架构


  React16 架构相较于 React15 增加了 Scheduler 调度器,用来调度任务,优先级高的任务优先进入 Reconciler 执行。

  在 React 中每一个 DOM 树结构,都有对应一个虚拟 DOM 树结构。React15 中使用普通的树结构表示虚拟 DOM,虚拟 DOM 节点的结构如图三所示,React16 使用链表结构表示虚拟 DOM,由之前的虚拟 DOM 节点升级为 Fiber 节点,Fiber 节点结构如图四所示。


图三 React15虚拟DOM节点


图四 React16 Fiber虚拟DOM节点


  其中,Fiber 节点中 type 属性标识元素的类型,key 属性和 type 属性可唯一标识一个元素,stateNode 属性标识 Fiber 节点对应的真实 DOM 节点,return、sibling 和 child 分别标识父 Fiber 节点、兄弟 Fiber 节点和子 Fiber 节点。flags 用来标记 Fiber 节点对应的真实 DOM 节点将要被执行的 DOM 操作,常见的操作有 Placement(插入)、Deletion(删除)和 Update(更新)等,对应的 flags 值分别为:5、8 和 4。


  在 React15 中,Reconciler 采用递归的方式更新子组件,更新一旦开始,中途就无法中断。React16 利用

Scheduler 和基于 Fiber 节点的链表结构的虚拟 DOM 实现了可中断异步更新。

三、Fiber 节点构成 Fiber 树

  在第二部分介绍了 Fiber 节点,那么 Fiber 节点是如何链接成 Fiber 树也就是虚拟 DOM 树呢?我们通过一个例子看一下。


funtion App() {  return (    <div>      <span>贝壳</span>      <span>大前端</span>    </div>  )}
复制代码


  上述代码片段中 function 组件对应的 Fiber 树如图五所示。


图五 App组件对应的Fiber树


  由图可以看出 Fiber 节点是依赖 return、sibling 和 child 这三个属性,将 Fiber 节点连接成 Fiber 树,即虚拟 DOM 树。

  在 React 中最多存在两颗 Fiber 树,当前屏幕上 DOM 结构对相应的 Fiber 树称为 current Fieber 树,在内存中构建的 Fiber 树称为 workInProgress Fiber 树。其中,Diff 算法的计算过程就是生成 workInProgress Fiber 树的过程,每次页面状态更新都会产生新的 workInProgress Fiber 树,当 workInProgress Fiber 树构建完成后交给 Renderer 渲染在页面上,之后在 React 中使用根节点的 current 指针完成由 current Fieber 树到 workInProgress Fiber 树的切换,此时

workInProgress Fiber 树就成为了 current Fiber 树,完成 DOM 更新。

四、基于 Fiber 的 React Diff

1、概念介绍

  首先从概念上介绍下 React Diff 算法,如图六所示,将要更新的 DOM 节点在更新时刻与四个节点有关:DOM 节点本身,DOM 节点对应的 JSX 对象,DOM 节点对应的 current Fiber 节点以及 workInProgress Fiber 节点,而 Diff 算法的本质是对比 JSX 对象和 current Fiber 节点,然后根据对比结果生成 workInProgress Fiber 节点,进而生成

workInProgress Fiber 树。其中需要执行相关操作的 Fiber 节点将会被打上 flags 标记,之后 Renderer 渲染器基于 Diff 过程中打上 flags 标记的 Fiber 节点链接成的链表进行相关的 DOM 操作。


图六 DOM节点相关节点

2、Diff 算法预设

  即使在最前沿的算法中,将前后两棵树完全比对的算法的复杂程度为 O(n3),为了降低算法复杂度,React 的 Diff 会预设三个限制:

(1)只对同级元素进行 Diff,Diff 算法只需对比节点当前所在层级;

(2)两个不同类型的元素会产生出不同的树,如果更新前后元素类型发生改变,则会新建节点及其子节点;

(3)开发者可为同层级的节点设置唯一 key 标识节点,以此暗示哪些子元素在不同的渲染下能保持稳定。

举个例子,如下所示:


// 更新前<div>  <p key="id1">节点1</p>  <span key="id2">节点2</span></div>// 更新后<div>  <span key="id2">节点2</span>  <p key="id1">节点1</p></div>
复制代码


  如果没有 key,React 会认为 div 的第一个子节点由 p 变为 span,第二个子节点由 span 变为 p,按照第二条预设,会新建节点 p 和节点 span。

  但若开发者使用了 key,指明了节点的对应关系,也就是说节点 p 和 span 只是交换了顺序,无需新建,可以进行复用。

  通过第一个预设,将 DOM 树的对比限制在了同一个层级进行对比,算法复杂度变为了 O(n),然后通过第三个预设使得同层级的节点通过自身的 key 能快速方便的找到变化后的节点。

3、Diff 算法入口函数介绍

  接下来,介绍下 Diff 算法入口函数。

  根据同级的节点数量将 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);}
复制代码


(1)单节点 Diff

  单节点 Diff 比较简单,先看下单节点 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,并返回 ...省略} 
复制代码


  React 首先判断 key 是否相同,如果 key 相同则判断 type 是否相同,只有都相同时一个 DOM 节点才能复用,如果可以复用,则直接使用 currrent Fiber 节点,无需在重新创建 Fiber 节点。

(2)多节点 Diff

  对于同级有多个元素的节点,Diff 算法要处理的情况相对复杂,但可以总结归纳为三种情况,第一种为节点新增或减少,第二种为节点更新,第三种为节点位置发生变化。举例如下。  情况 1 节点更新,如下所示,包括节点属性变化以及节点类型更新:


//更新前<div>  <span key="id1" className="before"></span>  <span key="id2"></span></div>// 节点属性变化 className 由before 变成了after<div>  <span key="id1" className="after"></span>  <span key="id2"></span></div>// 节点类型变化 第二个子元素由span 变成了div<div>  <span key="id1" className="before"></span>  <div key="id2"></div><div>
复制代码


情况 2 节点新增或减少,如下所示:


//情况2 节点新增 或减少 更新之前<div>   <span key="id1"></span>  <span key="id2"></span></div>
// 新增节点<div> <span key="id1"></span> <span kye="id2"></span> <span key="id3"></span></div>
//删除节点<div> <span key="id1"></span></div>
复制代码


情况 3 节点位置变化,如下所示:


// 情况3 节点位置变化  更新之前<div>  <span key="id1"></span>  <span key="id2"></span></div>
// 更新之后 位置发生了变化<div> <span key="id2"></span> <span key="id1"></span></div>
复制代码


  页面中所有同级有多个元素的节点的更新情况无非是以上的一种或多种场景的组合。


  但是,React 团队发现,在日常开发中,相对于增加和删除,更新组件发生的频率更高。所以 React Diff 会优先判断当前节点是否属于更新。


  基于以上原因,Diff 算法的整体逻辑会经历两轮遍历:


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

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


1)多节点 Diff 第一轮遍历

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


图七 React Diff算法流程图


  第一轮遍历产生了两个结果,结合例子分析一下,如下所示。


// 更新之前<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 都没遍历完,这意味着有节点在这次更新中改变了位置,需要进行第二轮遍历。

2)多节点 Diff 第二轮遍历

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

  const existingChildren = mapRemainingChildren(returnFiber,oldFiber)
复制代码


图八 Map结构


图八为打印的 Map 结构,接下来遍历剩余的 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,否则,不更新。

  结合上面的分析看下源代码,代码中注释了相关代码片段的功能。reconcileChildrenArray 函数入口以及传参和初始化参数


function reconcileChildrenArray(    returnFiber: Fiber,  //父节点    currentFirstChild: Fiber | null,  //current Fiber 节点    newChildren: Array<*>,  //JSX对象    lanes: Lanes,  ): Fiber | null {    // 函数返回的Fiber节点    let resultingFirstChild: Fiber | null = null;    let previousNewFiber: Fiber | null = null;    // oldFiber为链表    let oldFiber = currentFirstChild;    // 用来判断节点是否移动的参照物    let lastPlacedIndex = 0;    let newIdx = 0;     let nextOldFiber = null;  }
复制代码


  多节点 Diff 第一轮遍历的代码片段如下所示:


// 第一轮遍历,只遍历key相同的节点,key不同即跳出遍历for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {    if (oldFiber.index > newIdx) {        nextOldFiber = oldFiber;        oldFiber = null;    } else {        // 下次循环的旧Fiber节点:当前 oldFiber的兄弟节点        nextOldFiber = oldFiber.sibling;    }    // key相同返回fiber节点,key不同返回null    // 如果type相同复用节点,不同则确定该节点将会被删除,然后返回新节点,将oldFiber删除    const newFiber = updateSlot(  // 返回newFiber节点        returnFiber,        oldFiber,        newChildren[newIdx],        lanes,    );    // newFiber为null表示key不同,跳出第一轮循环    if (newFiber === null) {        if (oldFiber === null) {            oldFiber = nextOldFiber;        }        break;    }    // newFiber.alternate为null就是新节点,说明type不同创建了新fiber节点    if (oldFiber && newFiber.alternate === null) {    // 需要把oldFiber标记删除    deleteChild(returnFiber, oldFiber);    }    // 放置节点,更新lastPlacedIndex    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);    // 将新fiber链接到Fiber树    if (previousNewFiber === null) {        resultingFirstChild = newFiber;    } else {        previousNewFiber.sibling = newFiber;    }    previousNewFiber = newFiber;    //nextOldFiber节点为下一个循环的oldFiber节点    oldFiber = nextOldFiber;}// 第一轮遍历结束
复制代码


处理多节点 Diff 第一轮遍历结果代码片段如下所示:


// 处理第一轮遍历结果// 若第一轮遍历完后新节点数量少于旧节点数量// newChildren已经遍历完,将删除掉剩下的fiber节点if(newIdx === newChildren.length) {    deleteRemainingChildren(returnFiber, oldFiber);    return resultingFirstChild;}
// 若第一轮遍历完新节点数量大于旧节点数量// oldFiber已经遍历完,无节点可以复用,则创建新的节点if (oldFiber === null) { for (; newIdx < newChildren.length; newIdx++) { const newFiber = createChild(returnFiber, newChildren[newIdx], lanes); if (newFiber === null) { continue; } lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx); // 将新fiber链接到Fiber树 if (previousNewFiber === null) { resultingFirstChild = newFiber; } else { previousNewFiber.sibling = newFiber; } previousNewFiber = newFiber; } return resultingFirstChild;}// 处理第一轮遍历结果完成
复制代码


多节点 Diff 第二轮遍历的代码片段如下所示:


// 进行第二轮遍历// 还未处理的oldFiber存入以key为key,oldFiber为value的Map中,方便用key来获取对应的旧fiber节点const existingChildren = mapRemainingChildren(returnFiber, oldFiber);// 进入第二轮遍历,继续遍历剩余的newChildren节点,这些节点可能是需要移动或者删除的for (; newIdx < newChildren.length; newIdx++) {    // 从map中获取对应对应key的旧节点,返回更新后的新节点    const newFiber = updateFromMap(        existingChildren,        returnFiber,        newIdx,        newChildren[newIdx],        lanes,    );    if (newFiber !== null) {        // 若节点被复用,从map里删除老的节点,对应的情况可能是位置的改变        if (newFiber.alternate !== null) {            // 复用的节点要移除map,因为map里剩余的节点都会被标记Deletion删除            existingChildren.delete(                newFiber.key === null ? newIdx : newFiber.key,            );        }        // 放置节点同时节点判断是否移动        lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);        // 将新fiber链接到Fiber树        if (previousNewFiber === null) {            resultingFirstChild = newFiber;        } else {            previousNewFiber.sibling = newFiber;        }        previousNewFiber = newFiber;    }
}// 结束第二轮遍历
// 删除剩下的无用节点,并标记Deletion删除existingChildren.forEach(child => deleteChild(returnFiber, child));return resultingFirstChild;
复制代码

4、实战分析

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



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

1)第一轮遍历



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


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


2)第二轮遍历

此时的 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 树为:



  lastPlacedIndex 依旧为 3,此时 Map 为{C:C},继续遍历 newChildren 下一个节点 E,key 为 E 的节点在 Map 中不存在,此时就需要新建 E 节点,并为 E 节点打新增标签。


  此时的 workInProgress Fiber 树为:



  newChildren 遍历完成,此时 Map 为{C:C},下一步将 older Fiber 中的 C 节点打上 Deletion 标签,然后依次收集打上标签的节点,首先会将同级节点上需要删除的节点收集起来,然后依次收集其他打上标签的节点,收集好的节点连接成链表结构,如下图:



  Renderer 渲染器会依据生成的链表操作真实的 DOM,完成页面的更新操作。

五、总结

  相较于 React15,React16 利用 Scheduler 和基于 Fiber 节点的链表结构的虚拟 DOM 实现了可中断异步 DOM 更新,改善了页面 DOM 层级过深时造成的页面卡顿现象。React16 中的虚拟 DOM 树是由 Fiber 节点链接成的 Fiber 树,其中的每一个 Fiber 节点都有与之相对应的真实 DOM 节点。


  在 React 中最多存在两颗 Fiber 树,current Fiber 树和 workInProgress Fiber 树,Diff 算法的本质就是对比 current Fiber 节点和 JSX 对象,然后生成 workInProgress Fiber 树。根据同级的节点数量将 Diff 算法分为两类,单节点 Diff 和多节点 Diff。


  Diff 过程中通过 key 和 type 来对节点进行对比,如果更新前后节点的 key 和 type 相同,则节点可以被复用,否则,需要重建节点;同时会对需要更新、删除以及移动等操作的 Fiber 节点打上不同的标记,然后会将这些 Fiber 节点连接成链表。最后,Renderer 渲染器根据生成的链表执行实际的 DOM 操作,完成更新。

发布于: 2021 年 11 月 11 日阅读数: 16
用户头像

还未添加个人签名 2019.03.15 加入

还未添加个人简介

评论

发布
暂无评论
基于Fiber的React Diff算法源码分析