React中diff优化算法的了解

React中diff优化算法的了解

diff优化算法用于测算出Virtual DOM中更改的一部分，随后对于该一部分开展DOM实际操作，而无需再次3D渲染全部网页页面，3D渲染全部DOM构造的全过程中花销是非常大的，必须电脑浏览器对DOM构造开展重绘与流回，而diff优化算法可以促使操作流程中只升级改动的那一部分DOM构造而不升级全部DOM，那样可以降到最低实际操作DOM构造，可以较大 水平上降低电脑浏览器重绘与流回的经营规模。

虚似DOM

diff优化算法的基本是Virtual DOM，Virtual DOM是一棵以JavaScript目标做为基本的树，在React中一般是根据JSX编译程序而成的，每一个连接点称之为VNode，用目标特性来叙述连接点，事实上它是一层对真正DOM的抽象性，最后能够根据3D渲染实际操作使这棵树投射到真正自然环境上，简易而言Virtual DOM便是一个Js目标，用于叙述全部文本文档。
在电脑浏览器中搭建网页页面时必须应用DOM连接点叙述全部文本文档。

<div class="root" name="root">
    <p>1</p>
    <div>11</div>
</div>

假如应用Js目标去叙述以上的连接点及其文本文档，那麼便类似下边的模样，自然这不是React中用于叙述连接点的目标，React中建立一个React原素的有关源代码在react/src/ReactElement.js中，原文中的React版本号是16.10.2。

{
    type: "div",
    props: {
        className: "root"
        name: "root",
        children: [{
            type: "p",
            props: {
                children: [{
                    type: "text",
                    props: {
                        text: "1"
                    }
                }]
            }    
        },{
            type: "div",
            props: {
                children: [{
                    type: "text",
                    props: {
                        text: "11"
                    }
                }]
            }
        }]
    }
}

事实上在React16中开启了全新升级的构架Fiber，Fiber关键是完成了一个根据优先和requestIdleCallback的循环系统线程同步优化算法，有关难题没有文章内容中探讨，有关的难题大概取决于虚似DOM由树形结构转化成链表构造，原先的VDOM是一颗自上而下的树，根据深度优先解析xml，逐层递归算法直下，殊不知这一深度优先解析xml较大 的问题取决于不能终断，因而我们在diff patch又或是是Mount极大连接点的情况下，会导致很大的卡屏，React16的VDOM不会再是一颗自上而下这么简单的树，只是链表方式的虚似DOM，链表的每一个连接点是Fiber，而不是在16以前的虚似DOM连接点，每一个Fiber连接点纪录着众多信息内容，便于来到某一连接点的情况下终断，Fiber的构思是把3D渲染/更新过程(递归算法diff)拆分为一系列日常任务，每一次查验树枝的一小部分，做了看是不是也有時间再次下一个每日任务，有得话再次，沒有得话把自己挂起来，主线任务程很闲的情况下再再次。Fiber在diff环节，干了以下的实际操作，具体等同于在15的diff优化算法环节，干了优先的线程同步操纵。

• 把可终断的工作中拆分为日常任务。
• 对已经做的工作中调节优先选择顺序、改版、多路复用之前(没完成)工作中。
• diff环节线程同步优先操纵。

实际操作虚似DOM与实际操作原生态DOM的较为

在这儿直接引用了尤大得话(2016-02-08年的回应，这时Vue2.0还未公布，Vue2.0于2016-10-01上下公布，Vue2.0才添加虚似DOM)，有关连接为https://www.zhihu.com/question/31809713，提议融合连接中的难题阅读文章，还可以看一下难题中较为的实例，此外下边的回应也都十分的精粹。

原生态 DOM 实际操作 vs 根据架构封裝实际操作

这是一个特性vs可扩展性的选择，架构的实际意义取决于给你遮盖最底层的DOM实际操作，使你用更申明式的方法来叙述你的目地，进而使你的编码更非常容易维护保养，沒有一切架构能够比钢手动式的提升DOM实际操作更快，由于架构的DOM实际操作层必须解决一切顶层API很有可能造成的实际操作，它的完成务必是普适的，对于一切一个benchmark，我还能够写下比一切架构迅速的手动式提升，可是那有哪些实际意义呢?在搭建一个具体运用的情况下，你难道说为每一个地区都去做手动式提升吗?出自于可扩展性的考虑到，这显而易见不太可能，架构让你的确保是，你一直在不用手动式提升的状况下，我依旧能够让你给予凑合的特性。

对 React 的 Virtual DOM 的误会

React从来没有说过React比原生态实际操作DOM快，React的基本上思维方式是每一次有变化就全部再次3D渲染全部运用，要是没有Virtual DOM，简易来想便是立即重设innerHTML，很多人也没有意识到，在一个大中型目录全部数据信息都发生变化的状况下，重设innerHTML实际上是一个还算有效的实际操作，真真正正的难题是在所有再次3D渲染的思维方式下，即便仅有一行数据信息发生变化，它也必须重设全部innerHTML，此刻显而易见就会有很多的消耗。
我们可以较为一下innerHTML vs Virtual DOM的重绘特性耗费：

• innerHTML: render html string O(template size) 再次建立全部DOM原素O(DOM size)
• Virtual DOM: render Virtual DOM diff O(template size) 必需的DOM升级O(DOM change)。

Virtual DOM render diff显而易见比3D渲染html字符串数组要慢，可是!它仍然是纯js方面的测算，相比后边的DOM实际操作而言，仍然划算了过多，能够见到，innerHTML的总测算量无论是js测算或是DOM实际操作全是和全部页面的尺寸有关，但Virtual DOM的测算量里边，仅有js测算和页面尺寸有关，DOM实际操作是和数据信息的变化量有关的，前边讲了，和DOM实际操作比起來，js测算是极为划算的，这才算是为何要有Virtual DOM:它确保了 1)无论你的数据信息转变是多少，每一次重绘的特性都能够接纳; 2)你仍然可以用相近innerHTML的构思去写你的运用。

MVVM vs Virtual DOM

对比起React，别的MVVM系架构例如Angular, Knockout及其Vue、Avalon选用的全是数据信息关联:根据Directive/Binding目标，观查数据信息转变并保存对具体DOM原素的引入，当有数据信息转变时开展相匹配的实际操作，MVVM的转变查验是数据信息方面的，而React的查验是DOM构造方面的，MVVM的特性也依据变化检验的完成基本原理各有不同: Angular的脏查验促使一切变化都是有固定不动的O(watcher count)的成本; Knockout/Vue/Avalon都选用了依靠搜集，在js和DOM方面全是O(change):

• 脏查验：scope digest O(watcher count) 必需DOM升级O(DOM change)。
• 依靠搜集：再次搜集依靠O(data change) 必需DOM升级 O(DOM change)。

能够见到，Angular最不高效率的地区取决于一切小变化都是有的和watcher总数有关的特性成本，可是!当全部数据信息都发生变化的情况下，Angular实际上并不吃大亏，依靠搜集在复位和数据信息转变的情况下都必须再次搜集依靠，这一成本在少量升级的情况下基本上能够忽视，但在信息量巨大的情况下也会造成一定的耗费。
MVVM3D渲染目录的情况下，因为每一行都是有自身的数据信息修饰符，因此 一般全是每一行有一个相匹配的ViewModel案例，或是是一个略微轻巧一些的运用原形承继的scope目标，但也是有一定的成本，因此 MVVM目录3D渲染的复位基本上一定比React慢，由于建立ViewModel / scope案例相比Virtual DOM而言要价格昂贵许多 ，这儿全部MVVM完成的一个一同难题便是在目录3D渲染的数据库变化时，尤其是当数据信息是全新升级的目标时，怎样合理地多路复用早已建立的ViewModel案例和DOM原素，倘若沒有一切多路复用层面的提升，因为数据信息是全新升级的，MVVM事实上必须消毁以前的全部案例，再次建立全部案例，最终再开展一次3D渲染!这就是为何题型里连接的angular/knockout完成都相对性较慢，比较之下，React的变化查验因为是DOM构造方面的，即便是全新升级的数据信息，只需最终3D渲染結果没变，那麼就不用做瞎忙。
顺路说一句，React3D渲染目录的情况下也必须给予key这一独特prop，实质上和track-by是一回事儿。

特性较为也需看场所

在较为特性的情况下，要分清晰原始3D渲染、少量数据信息升级、很多数据信息升级这种不一样的场所，Virtual DOM、脏查验MVVM、数据采集MVVM在不一样场所各不相同的主要表现和不一样的提升要求，Virtual DOM为了更好地提高少量数据信息升级时的特性，也必须目的性的提升，例如shouldComponentUpdate或者immutable data。

• 原始3D渲染：Virtual DOM > 脏查验 >= 依靠搜集。
• 少量数据信息升级：依靠搜集 >> Virtual DOM 提升 > 脏查验(没法提升) > Virtual DOM无提升。
• 很多数据信息升级：脏查验 提升 >= 依靠搜集 提升 > Virtual DOM(没法/不用提升) >> MVVM无提升。

不必纯真地认为Virtual DOM便是快，diff并不是完全免费的，batching么MVVM也可以做，并且最后patch的情况下还并不是要用原生态API，我认为Virtual DOM真真正正的使用价值几乎都并不是特性，只是它 1)为涵数式的UI程序编写方法打开了大门口; 2)能够3D渲染到DOM之外的backend，例如ReactNative。

汇总

之上这种较为，大量的是针对架构开发设计学者给予一些参照，流行的架构 有效的提升，足够解决绝大多数运用的性能测试方案，如果是对特性有完美要求的特殊情况，实际上应当放弃一些可扩展性采用手动式提升:例如Atom在线编辑器在文档3D渲染的完成上放弃了React而选用了自身完成的tile-based rendering; 又例如在手机端必须DOM-pooling的虚似翻转，不用考虑到次序转变，能够绕开架构的内嵌完成自身搞一个。

diff优化算法

React在运行内存中维护保养一颗虚似DOM树，当数据信息发生改变时(state & props)，会全自动的升级虚似DOM，得到一个新的虚似DOM树，随后根据Diff优化算法，较为新老虚似DOM树，找到最少的有转变的一部分，将这一转变的一部分Patch添加序列，最后大批量的升级这种Patch到具体的DOM中。

算法复杂度

最先开展一次详细的diff必须O(n^3)的算法复杂度，这是一个最小编辑距离的难题，在较为字符串数组的最少编辑距离时应用动态规划的计划方案必须的算法复杂度是O(mn)，可是针对DOM而言是一个树结构，而树结构的最少编辑距离难题的算法复杂度在30很多年的演变中从O(m^3n^3)演进到了O(n^3)，有关这个问题如果有兴趣爱好得话能够科学研究一下毕业论文https://grfia.dlsi.ua.es/ml/algorithms/references/editsurvey_bille.pdf。
针对本来要想提高工作效率而引进的diff优化算法应用O(n^3)的算法复杂度显而易见不是太适合的，如果有1000个连接点原素将必须开展十亿次较为，这是一个价格昂贵的优化算法，因此 务必有一些让步来提高速度，对较为根据一些对策开展简单化，将算法复杂度变小到O(n)，尽管并并不是最少编辑距离，可是做为编辑距离与時间特性的综合性考虑是一个比较好的解决方法，是一种比较好的最合适的计划方案。

diff对策

上面提及的O(n)算法复杂度是根据一定对策开展的，React文本文档中提及了2个假定：

• 2个不一样种类的原素将造成不一样的树。
• 根据渲染器附加key特性，开发人员能够提示什么子原素可能是平稳的。

简单点说便是：

• 只开展统一等级的较为，假如跨等级的挪动则视作建立和删掉实际操作。
• 如果是不一样种类的原素，则觉得是建立了新的原素，而不容易递归算法较为她们的小孩。
• 如果是目录原素等较为类似的內容，能够根据key来唯一明确是挪动或是建立或删掉实际操作。

较为后会发生几类状况，随后开展相对应的实际操作：

• 此连接点被加上或清除->加上或清除新的连接点。
• 特性被更改->旧特性改成新特性。
• 文字內容被更改->旧內容改成新內容。
• 连接点tag或key是不是更改->更改则清除后建立新元素。

剖析

在剖析的时候会简易引入一下在React的源代码，起輔助功效的编码，具体源代码是很繁杂的，引入的是一部分精彩片段协助了解，文中的源代码TAG为16.10.2。
有关if (__DEV__){...}有关编码事实上是为更强的开发人员感受而撰写的，React中的友善的出错，render功能测试这些编码全是写在if (__DEV__)中的，在production build的情况下，这种编码不容易被装包，因而我们可以毫无顾忌的给予专为开发人员服务项目的编码，React的最佳实践之一便是在开发设计时应用development build，在工作环境应用production build，因此 大家事实上能够先绕过这一部分编码，致力于了解比较关键的一部分。
大家剖析diff优化算法是以reconcileChildren逐渐的，以前从 setState -> enqueueSetState(UpdateQueue) -> scheduleUpdate -> performWork -> workLoop -> beginWork -> finishClassComponent -> reconcileChildren有关的一部分就但是多详细介绍了，必须留意的是beginWork会将一个一个的Fiber来开展diff，期内是可终断的，由于每一次实行下一个Fiber的核对时，都是会先分辨这一帧剩下的時间是不是充裕，链表的每一个连接点是Fiber，而不是在16以前的虚似DOM连接点，每一个Fiber都是有React16的diff对策选用从链表头顶部逐渐较为的优化算法，是链条式的深度优先解析xml，即早已从树结构变成了链表构造，具体等同于在15的diff优化算法环节，干了优先的线程同步操纵。除此之外，每一个Fiber都是会有一个child、sibling、return三大特性做为连接树前后左右的表针；child做为仿真模拟树形结构的构造表针；effectTag一个很有趣的标识，用以纪录effect的种类，effect指的便是对DOM实际操作的方法，例如改动，删掉等实际操作，用以到后边开展commit(相近数据库查询)；firstEffect、lastEffect等东西是用于储存终断前后左右effect的情况，客户终断后修复以前的实际操作及其tag用以标识。
reconcileChildren完成的便是武林上广为人知的Virtul DOM diff，其事实上仅仅一个通道涵数，假如初次3D渲染，current空null，就根据mountChildFibers建立子连接点的Fiber案例，要不是初次3D渲染，就启用reconcileChildFibers去做diff，随后得到effect list。

// react-reconciler/src/ReactChildFiber.js line 1246
export function reconcileChildren(
  current: Fiber | null,
  workInProgress: Fiber,
  nextChildren: any,
  renderExpirationTime: ExpirationTime,
) {
  if (current === null) { // 初次3D渲染 建立子连接点的`Fiber`案例
    workInProgress.child = mountChildFibers(
      workInProgress,
      null,
      nextChildren,
      renderExpirationTime,
    );
  } else { // 不然启用`reconcileChildFibers`去做`diff`
    workInProgress.child = reconcileChildFibers(
      workInProgress,
      current.child,
      nextChildren,
      renderExpirationTime,
    );
  }
}

比照一下mountChildFibers和reconcileChildFibers有什么不同，能够看得出她们全是根据ChildReconciler工厂函数来的，仅仅传送的主要参数不一样罢了，这一主要参数叫shouldTrackSideEffects，他的功效是分辨是不是要提升一些effectTag，主要是用于提升第一次3D渲染的，由于第一次3D渲染沒有升级实际操作。ChildReconciler是一个非常长的加工厂(包裝)涵数，內部有很多helper涵数，最后回到的涵数叫reconcileChildFibers，这一涵数完成了对联fiber连接点的reconciliation。

// react-reconciler/src/ReactChildFiber.js line 1370
export const reconcileChildFibers = ChildReconciler(true);
export const mountChildFibers = ChildReconciler(false);

function ChildReconciler(shouldTrackSideEffects) { 
  // ...
  function deleteChild(){
      // ...
  }
  function useFiber(){
      // ...
  }
  function placeChild(){
      // ...
  }
  function placeSingleChild(){
      // ...
  }
  function updateTextNode(){
      // ...
  }
  function updateElement(){
      // ...
  }
  function updatePortal(){
      // ...
  }
  function updateFragment(){
      // ...
  }
  function createChild(){
      // ...
  }
  function updateSlot(){
      // ...
  }
  function updateFromMap(){
      // ...
  }
  function warnOnInvalidKey(){
      // ...
  }
  function reconcileChildrenArray(){
      // ...
  }
  function reconcileChildrenIterator(){
      // ...
  }
  function reconcileSingleTextNode(){
      // ...
  }
  function reconcileSingleElement(){
      // ...
  }
  function reconcileSinglePortal(){
      // ...
  }
  function reconcileChildFibers(){
      // ...
  }
  return reconcileChildFibers;
}

reconcileChildFibers便是diff一部分的行为主体编码，有关实际操作都是在ChildReconciler涵数中，在这个涵数中有关主要参数，returnFiber是将要diff的这层的父节点，currentFirstChild是当今层的第一个Fiber连接点，newChild是将要升级的vdom连接点(可能是TextNode、可能是ReactElement，可能是二维数组)，并不是Fiber连接点。expirationTime是到期時间，这一主要参数是跟生产调度有关系的，跟diff沒有很大关联，此外必须留意的是，reconcileChildFibers 是reconcile(diff)的一层构造。

最先看TextNode的diff，他是非常简单的，针对diff TextNode会出现二种状况：

• currentFirstNode是TextNode。
• currentFirstNode并不是TextNode。

分二种状况缘故便是为了更好地多路复用连接点，第一种状况，xxx是一个TextNode，那麼就意味着这这一连接点能够多路复用，有多路复用的连接点，对性能优化很有协助，即然新的child只有一个TextNode，那麼多路复用连接点以后，就把剩余的aaa连接点就可以删除了，那麼div的child就可以加上到workInProgress中来到。useFiber便是多路复用连接点的方式，deleteRemainingChildren便是删掉剩下连接点的方式，这儿是以currentFirstChild.sibling逐渐删掉的。

if (currentFirstChild !== null && currentFirstChild.tag === HostText) {
  // We already have an existing node so let's just update it and delete
  // the rest.
  deleteRemainingChildren(returnFiber, currentFirstChild.sibling); // 删掉弟兄
  const existing = useFiber(currentFirstChild, textContent, expirationTime);
  existing.return = returnFiber;
  return existing; // 多路复用
}

第二种状况，xxx并不是一个TextNode，那麼就意味着这一连接点不可以多路复用，因此 就从currentFirstChild逐渐删除剩下的连接点，在其中createFiberFromText便是依据textContent来建立连接点的方式，除此之外删掉连接点不容易确实从链表里边把连接点删掉，仅仅打一个delete的tag，当commit的情况下才会真真正正的去删掉。

// The existing first child is not a text node so we need to create one
// and delete the existing ones.
// 建立新的Fiber连接点，将旧的连接点和旧连接点的弟兄都删掉 
deleteRemainingChildren(returnFiber, currentFirstChild);
const created = createFiberFromText(
  textContent,
  returnFiber.mode,
  expirationTime,
);

下面是React Element的diff，这时大家解决的是该连接点的父节点仅有此连接点一个连接点的状况，与上边TextNode的diff相近，她们的构思是一致的，先找是否有能够多路复用的连接点，要是没有就此外建立一个。这时会采用上面的2个假定用于分辨连接点是不是能够多路复用，即key是不是同样，连接点种类是不是同样，假如之上同样，则能够觉得这一连接点仅仅转变了內容，不用建立新的连接点，能够多路复用的。假如连接点的种类不同样，就将连接点从当今连接点逐渐把剩下的都删掉。在搜索可多路复用连接点的情况下，其并并不是只致力于第一个连接点是不是可多路复用，只是再次在该层中循环系统寻找一个能够多路复用的连接点，最高层的while及其底端的child = child.sibling;是为了更好地再次从子连接点中寻找一个key与tag同样的可多路复用连接点，此外删掉连接点不容易确实从链表里边把连接点删掉，仅仅打一个delete的tag，当commit的情况下才会真真正正的去删掉。

// react-reconciler/src/ReactChildFiber.js line 1132
const key = element.key;
let child = currentFirstChild;
while (child !== null) {
  // TODO: If key === null and child.key === null, then this only applies to
  // the first item in the list.
  if (child.key === key) {
    if (
      child.tag === Fragment
        ? element.type === REACT_FRAGMENT_TYPE
        : child.elementType === element.type ||
          // Keep this check inline so it only runs on the false path:
          (__DEV__
            ? isCompatibleFamilyForHotReloading(child, element)
            : false)
    ) {
      deleteRemainingChildren(returnFiber, child.sibling); // 由于当今连接点是只有一个连接点，而老的如果是有弟兄连接点是要删掉的，是不必要的
      const existing = useFiber(
        child,
        element.type === REACT_FRAGMENT_TYPE
          ? element.props.children
          : element.props,
        expirationTime,
      );
      existing.ref = coerceRef(returnFiber, child, element);
      existing.return = returnFiber;
      // ...
      return existing;
    } else {
      deleteRemainingChildren(returnFiber, child);
      break;
    }
  } else {
    deleteChild(returnFiber, child); // 从child逐渐delete
  }
  child = child.sibling; // 再次从子连接点中寻找一个可多路复用的连接点
}

下面便是沒有寻找能够多路复用的连接点因此去建立连接点了，针对Fragment连接点和一般的Element连接点建立的方法不一样，由于Fragment原本便是一个无意义的连接点，他真真正正必须建立Fiber的是它的children，而不是它自身，因此 createFiberFromFragment传送的并不是element，只是element.props.children。

// react-reconciler/src/ReactChildFiber.js line 1178
if (element.type === REACT_FRAGMENT_TYPE) {
  const created = createFiberFromFragment(
    element.props.children,
    returnFiber.mode,
    expirationTime,
    element.key,
  );
  created.return = returnFiber;
  return created;
} else {
  const created = createFiberFromElement(
    element,
    returnFiber.mode,
    expirationTime,
  );
  created.ref = coerceRef(returnFiber, currentFirstChild, element);
  created.return = returnFiber;
  return created;
}

diff Array算作diff中最繁杂的一部分了，干了许多 的提升，由于Fiber树是单链表构造，沒有子连接点二维数组那样的算法设计，也就沒有能够供两边另外较为的尾端游标卡尺，因此 React的这一优化算法是一个简单化的二端比较分析法，只从头顶部逐渐较为，在Vue2.0中的diff优化算法在patch时则是立即应用的二端比较分析法完成的。
最先考虑到同样部位开展比照，这个是较为非常容易想起的一种方法，即在做diff的情况下就可以从新老的二维数组中依照数据库索引一一比照，假如能多路复用，就把这个连接点从老的链表里边删掉，不可以多路复用得话再开展别的的多路复用对策。这时的newChildren二维数组是一个VDOM二维数组，因此 在这儿应用updateSlot包裝成newFiber。

// react-reconciler/src/ReactChildFiber.js line 756
function reconcileChildrenArray(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    newChildren: Array<*>,
    expirationTime: ExpirationTime,
  ): Fiber | null {
    // 机翻注解
    // 这一优化算法不可以根据两边检索来提升，由于我们在光纤线上沒有反方向表针。我要看看大家可用这一实体模型走多远。假如最后不值衡量，我们可以稍候再加上。
    // 即便是二端提升，大家也期待在非常少有转变的状况下开展提升，并强制性开展较为，而不是寻找地形图。它想探寻在前行方式下最先抵达哪条途径，而且仅有在我们注意到大家必须许多 向前走的情况下才去地形图。这不可以解决翻转及其2个完毕的检索，但它是不寻常的。除此之外，要使两边提升在Iterables上工作中，大家必须拷贝全部结合。
    // 在第一次迭代更新中，大家只需在每一次插进/挪动时都遇到坏状况（将全部內容加上到投射中）。
    // 假如变更此编码，还必须升级reconcileChildrenIterator()，它应用同样的优化算法。
    let oldFiber = currentFirstChild;
    let lastPlacedIndex = 0;
    let newIdx = 0;
    let nextOldFiber = null;
     // 第一个for循环，依照index一一比照，当新老用户连接点不一致时撤出循环系统而且纪录撤出时的连接点及oldFiber连接点
    for (; oldFiber !== null && newIdx < newChildren.length; newIdx  ) {
      if (oldFiber.index > newIdx) { // 部位不配对
        nextOldFiber = oldFiber;  // 下一个将要比照的旧连接点
        oldFiber = null; // 假如newFiber也为null(不可以多路复用)就撤出当今一一比照的for循环
      } else {
        nextOldFiber = oldFiber.sibling; //一切正常的状况下 为了更好地下轮循环系统，取得弟兄连接点下边取值给oldFiber
      }
      // //假如连接点能够多路复用(key值配对)，就升级而且回到新连接点，不然回到为null，意味着连接点不能多路复用
      const newFiber = updateSlot( // 分辨是不是能够多路复用连接点
        returnFiber,
        oldFiber,
        newChildren[newIdx],
        expirationTime,
      );
      // 连接点没法多路复用 跳出循环
      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);
        }
      }
      // 此次解析xml会给增加的连接点打 插进的标识
      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;  // 再次给 oldFiber 取值再次解析xml
  }

在updateSlot方式中界定了分辨是不是能够多路复用，针对文字连接点,假如key不以null，那麼就意味着老连接点并不是TextNode，而新连接点也是TextNode，因此 回到null，不可以多路复用，相反则能够多路复用，启用updateTextNode方式，留意updateTextNode里边包括了初次3D渲染的情况下的逻辑性，初次3D渲染的情况下回插进一个TextNode，而不是多路复用。

// react-reconciler/src/ReactChildFiber.js line 544
function updateSlot(
    returnFiber: Fiber,
    oldFiber: Fiber | null,
    newChild: any,
    expirationTime: ExpirationTime,
  ): Fiber | null {
    // Update the fiber if the keys match, otherwise return null.

    const key = oldFiber !== null ? oldFiber.key : null;

    if (typeof newChild === 'string' || typeof newChild === 'number') {
      // 针对新的连接点如果是 string 或是 number，那麼全是沒有 key 的，
      // 全部假如老的连接点有 key 得话，就不可以多路复用，立即回到 null。
      // 老的连接点 key 为 null 得话，意味着老的连接点是文字连接点，就可以多路复用
      if (key !== null) {
        return null;
      }
      return updateTextNode(
        returnFiber,
        oldFiber,
        ''   newChild,
        expirationTime,
      );
    }

    // ...

    return null;
}

newChild是Object的情况下大部分与ReactElement的diff相近，仅仅沒有while了，分辨key和原素的种类是不是相同来分辨是不是能够多路复用。最先分辨是不是目标，用的是typeof newChild === object&&newChild!== null，留意得加!== null，由于typeof null也是object，随后根据$$typeof分辨是REACT_ELEMENT_TYPE或是REACT_PORTAL_TYPE，各自启用不一样的多路复用逻辑性，随后因为二维数组也是Object，因此 这一if里边也是有二维数组的多路复用逻辑性。

// react-reconciler/src/ReactChildFiber.js line 569
if (typeof newChild === 'object' && newChild !== null) {
  switch (newChild.$$typeof) {
    case REACT_ELEMENT_TYPE: { // ReactElement 
      if (newChild.key === key) {
        if (newChild.type === REACT_FRAGMENT_TYPE) {
          return updateFragment(
            returnFiber,
            oldFiber,
            newChild.props.children,
            expirationTime,
            key,
          );
        }
        return updateElement(
          returnFiber,
          oldFiber,
          newChild,
          expirationTime,
        );
      } else {
        return null;
      }
    }
    case REACT_PORTAL_TYPE: {
      // 启用 updatePortal
      // ...
    }
  }

  if (isArray(newChild) || getIteratorFn(newChild)) {
    if (key !== null) {
      return null;
    }

    return updateFragment(
      returnFiber,
      oldFiber,
      newChild,
      expirationTime,
      null,
    );
  }
}

使我们回到起点的解析xml，在我们解析xml完成了以后，便会有二种状况，即老连接点早已解析xml结束，或是新连接点早已解析xml结束，假如这时大家新连接点早已解析xml完毕，也就是沒有要升级的了，这类状况一般就是以原先的二维数组里边删除了原素，那麼立即把剩余的老连接点删除了就可以了。假如老的连接点在第一次循环系统的情况下就被多路复用完后，新的连接点也有，很有可能便是增加了连接点的状况，那麼这个时候只必须依据把剩下新的连接点立即建立Fiber就可以了。

// react-reconciler/src/ReactChildFiber.js line 839
// 新连接点早已升级进行，删掉不必要的老连接点
if (newIdx === newChildren.length) {
  // We've reached the end of the new children. We can delete the rest.
  deleteRemainingChildren(returnFiber, oldFiber);
  return resultingFirstChild;
}

// 新连接点早已升级进行，删掉不必要的老连接点
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],
      expirationTime,
    );
    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;
}

下面考虑到挪动的状况怎样开展连接点多路复用，即假如老的二维数组和新的二维数组里边都是有这一原素，并且部位不同样这类状况下的多路复用，React把全部老二维数组原素按key或是是index放Map里，随后解析xml新二维数组，依据新二维数组的key或是index迅速寻找老二维数组里边是不是有可多路复用的，原素有key就Map的键就存key，沒有key就存index。

// react-reconciler/src/ReactChildFiber.js line 872
// Add all children to a key map for quick lookups.
// 从oldFiber逐渐将早已存有的连接点的key或是index加上到map构造中
const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

// Keep scanning and use the map to restore deleted items as moves.
// 剩下沒有比照的新连接点，到旧连接点的map中根据key或是index一一比照查询是不是能够多路复用。
for (; newIdx < newChildren.length; newIdx  ) {
  // 关键查询新老连接点的key或是index是不是有同样的，随后再查询是不是能够多路复用。
  const newFiber = updateFromMap(
    existingChildren,
    returnFiber,
    newIdx,
    newChildren[newIdx],
    expirationTime,
  );
  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(  // 在map中删掉掉早已多路复用的连接点的key或是index
          newFiber.key === null ? newIdx : newFiber.key,
        );
      }
    }
    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
    // 加上newFiber到升级过的newFiber构造中。
    if (previousNewFiber === null) {
      resultingFirstChild = newFiber;
    } else {
      previousNewFiber.sibling = newFiber;
    }
    previousNewFiber = newFiber;
  }
}

// react-reconciler/src/ReactChildFiber.js line 299
// 将旧连接点的key或是index，旧连接点储存到map构造中，便捷根据key或是index获得
function mapRemainingChildren(
    returnFiber: Fiber,
    currentFirstChild: Fiber,
  ): Map<string | number, Fiber> {
    // Add the remaining children to a temporary map so that we can find them by
    // keys quickly. Implicit (null) keys get added to this set with their index
    // instead.
    const existingChildren: Map<string | number, Fiber> = new Map();

    let existingChild = currentFirstChild;
    while (existingChild !== null) {
      if (existingChild.key !== null) {
        existingChildren.set(existingChild.key, existingChild);
      } else {
        existingChildren.set(existingChild.index, existingChild);
      }
      existingChild = existingChild.sibling;
    }
    return existingChildren;
  }

到此新数组遍历结束，也就是同一层的diff全过程结束，我们可以把全部全过程分成三个环节:

• 第一解析xml新二维数组，新老用户二维数组同样index开展比照，根据updateSlot方式寻找能够多路复用的连接点，直至寻找不能多路复用的连接点就撤出循环系统。
• 第一解析xml完以后，删掉剩下的老连接点，增加剩下的新连接点的全过程，如果是新连接点已解析xml进行，就将剩下的老连接点批量删除;如果是老连接点解析xml进行仍有新连接点剩下，则将新连接点插入。
• 把全部老二维数组原素按key或index放Map里，随后解析xml新二维数组，插进老二维数组的原素，它是挪动的状况。

每日一题

https://GitHub.com/WindrunnerMax/EveryDay

参照

https://zhuanlan.zhihu.com/p/89363990
https://zhuanlan.zhihu.com/p/137251397
https://github.com/sisterAn/blog/issues/22
https://github.com/hujiulong/blog/issues/6
https://juejin.cn/post/6844904165026562056
https://www.cnblogs.com/forcheng/p/13246874.html
https://zh-hans.reactjs.org/docs/reconciliation.html
https://zxc0328.github.io/2017/09/28/react-16-source/
https://blog.csdn.net/halations/article/details/109284050
https://blog.csdn.net/susuzhe123/article/details/107890118
https://github.com/Advanced-Frontend/Daily-Interview-Question/issues/47
https://github.com/jianjiachenghub/react-deeplearn/blob/master/学习心得/React16源代码分析6-Fiber链条式diff优化算法.md