基于Fiber的ReactDiff算法源码分析

见贤思齐

基于Fiber的React Diff算法源码分析 基于Fiber的React Diff算法源码分析 王丹丹@贝壳找房 贝壳产品技术 贝壳产品技术 “贝壳产品技术公众号”作为贝壳官方产品技术号，致力打造贝壳产品、技术干货分享平台，面向互联网/O2O开发/产品从业者，每周推送优质产品技术文章、技术沙龙活动及招聘信息等。欢迎大家关注我们。 242篇内容 2021年11月05日 18:28 一、简介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 React16React15将整体架构分为了两层，如图一所示，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树呢？我们通过一个例子看一下：funtionApp(){return(贝壳大前端)}上述代码片段中function 组件对应的Fiber树如图五所示。图五 function 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 Diff1、概念介绍首先从概念上介绍下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标识节点，以此暗示哪些子元素在不同的渲染下能保持稳定。举个例子，如下所示：//更新前 节点1节点2//更新后节点2 节点1如果没有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函数入口代码如下述所示：functionreconcileChildFibers(returnFiber:Fiber,currentFirstChild:Fiber|null,newChild:any,):Fiber|null{constisObject=typeofnewChild==='object'&newChild!==null;if(isObject){//object类型，可能是REACT_ELEMENT_TYPE或REACT_PORTAL_TYPEswitch(newChild.$typeof){caseREACT_ELEMENT_TYPE://调用reconcileSingleElement处理//...其他case}}if(typeofnewChild==='string'||typeofnewChild==='number'){//调用reconcileSingleTextNode处理}if(isArray(newChild)){//调用reconcileChildrenArray处理}//以上都没有命中，删除节点returndeleteRemainingChildren(returnFiber,currentFirstChild);}（1）单节点Diff单节点Diff比较简单，先看下单节点Diff函数，源代码如下所示：functionreconcileSingleElement(returnFiber:Fiber,currentFirstChild:Fiber|null,element:ReactElement):Fiber{constkey=element.key;letchild=currentFirstChild;//首先判断是否存在对应DOM节点while(child!==null){//上一次更新存在DOM节点，接下来判断是否可复用//首先比较key是否相同if(child.key===key){//key相同，接下来比较type是否相同switch(child.tag){//...省略casedefault:{if(child.elementType===element.type){//type相同则表示可以复用//返回复用的fiberreturnexisting;}//type不同则跳出switchbreak;}}//不能复用的节点，被标记为删除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 节点更新，如下所示，包括节点属性变化以及节点类型更新：//更新前//节点属性变化className由before变成了after//节点类型变化第二个子元素由span变成了div情况2 节点新增或减少，如下所示：//情况2节点新增或减少更新之前//新增节点//删除节点情况3 节点位置变化，如下所示：//情况3节点位置变化更新之前//更新之后位置发生了变化页面中所有同级有多个元素的节点的更新情况无非是以上的一种或多种场景的组合。但是，React团队发现，在日常开发中，相对于增加和删除，更新组件发生的频率更高。所以React Diff会优先判断当前节点是否属于更新。基于以上原因，Diff算法的整体逻辑会经历两轮遍历：第一轮遍历：处理更新的节点第二轮遍历：处理剩下的不属于更新的节点。1）多节点Diff第一轮遍历第一轮遍历的目的是处理更新节点，处理流程图如图七所示，其中的newChildren为被转译后的JSX 对象，orderFiber为链表结构的current Fiber树。图七 React diff 算法流程图第一轮遍历产生了两个结果，结合例子分析一下，如下所示。//更新之前12//更新之后情况1newChildren与oldFiber都遍历完12//更新之后情况2newChildren没遍历完，oldFiber遍历完123//更新之后情况3newChildren遍历完，oldFiber没遍历完1结果一：可能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也没有遍历完。举个例子，如下所示：//更新之前123//更新之后132newChildren与oldFiber都没遍历完，这意味着有节点在这次更新中改变了位置，需要进行第二轮遍历。2）多节点Diff第二轮遍历因为第二轮遍历需要处理改变位置的节点，所以为了方便找到拥有同一个key的newChildren和olderFiber节点，react团队将所有还未处理的oldFiber存入以key为key，oldFiber为value的Map中。图八 Map结构图八为打印的Map结构，接下来遍历剩余的newChildren，通过newChildren[i].key就能很快在existingChildren中找到key相同的oldFiber节点。因为有节点的位置发生了移动，所以需要选一个参照的节点，来判断其他的节点是否移动，React选定最后一个可复用的节点为参照物，记下其在oldFiber中的位置索引，用变量lastPlacedIndex表示。由于更新中节点是按newChildren的顺序排列，所以在遍历newChildren过程中，每个遍历到的可复用节点一定是当前遍历到的所有可复用节点中最靠右的那个。用变量oldIndex表示遍历到的可复用节点在oldFiber中的位置索引，如果oldIndex lastPlacedIndex代表该节点不需要被移动。其中，lastPlacedIndex初始为0，更新lastPlacedIndex规则为：每遍历一个可复用的节点，如果oldIndex >= lastPlacedIndex，则更新lastPlacedIndex为oldIndex，否则，不更新。结合上面的分析看下源代码，代码中注释了相关代码片段的功能。reconcileChildrenArray 函数入口以及传参和初始化参数。functionreconcileChildrenArray(returnFiber:Fiber,//父节点currentFirstChild:Fiber|null,//currentFiber节点newChildren:Array,//JSX对象lanesanes,):Fiber|null{//函数返回的Fiber节点letresultingFirstChild:Fiber|null=null;letpreviousNewFiber:Fiber|null=null;//oldFiber为链表letoldFiber=currentFirstChild;//用来判断节点是否移动的参照物letlastPlacedIndex=0;letnewIdx=0;letnextOldFiber=null;}多节点Diff第一轮遍历的代码片段如下所示：//第一轮遍历，只遍历key相同的节点，key不同即跳出遍历for(;oldFiber!==null&newIdxnewIdx){nextOldFiber=oldFiber;oldFiber=null;}else{//下次循环的旧Fiber节点：当前 oldFiber的兄弟节点nextOldFiber=oldFiber.sibling;}//key相同返回fiber节点，key不同返回null//如果type相同复用节点，不同则确定该节点将会被删除，然后返回新节点，将oldFiber删除constnewFiber=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);}//放置节点,更新lastPlacedIndexlastPlacedIndex=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);returnresultingFirstChild;}//若第一轮遍历完新节点数量大于旧节点数量//oldFiber已经遍历完,无节点可以复用，则创建新的节点if(oldFiber===null){for(;newIdxdeleteChild(returnFiber,child));returnresultingFirstChild;3. 实例分析下面通过一个例子阐述下整个Diff 过程，为了简化Diff过程，其中的ABCD表示DOM树的节点，字母的值表示节点的key。如上图所示，app节点下有顺序为ABCD四个节点，若将app节点下变为ADBE，Diff 算法会经历下面的过程。第一轮遍历第一轮遍历newChildren开始，节点A可复用，此时的workInProgress Fiber树为继续遍历下一个节点，因newChildren第二个节点D和oldFiber 中下一个节点B的key不相同跳出第一轮遍历，进行第二轮遍历。 2.第二轮遍历此时的olderFiber和newChildren如下：此时lastPlacedIndex为0，Map为{B:B，C:C，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