diff react 源码_react diff算法源码 - CSDN
  • 在《React源码分析 - 组件更新与事务》中的流程图的最后: 蓝色框框的部分分别是Diff算法的核心代码updateChildren以及processUpdates,通过Diff算法获取了组件更新的...

    在《React源码分析 - 组件更新与事务》中的流程图的最后:

    diff update

    蓝色框框的部分分别是Diff算法的核心代码updateChildren以及processUpdates,通过Diff算法获取了组件更新的updates队列之后一次性进行更新。

    Diff算法的代码(先别着急下面会具体解释算法的主要步骤):

        _updateChildren: function (nextNestedChildrenElements, transaction, context) {
          var prevChildren = this._renderedChildren;
          var removedNodes = {};
          var nextChildren = this._reconcilerUpdateChildren(prevChildren, nextNestedChildrenElements, removedNodes, transaction, context);
          if (!nextChildren && !prevChildren) {
            return;
          }
          var updates = null;
          var name;
          var lastIndex = 0;
          var nextIndex = 0;
          var lastPlacedNode = null;
          for (name in nextChildren) {
            if (!nextChildren.hasOwnProperty(name)) {
              continue;
            }
            var prevChild = prevChildren && prevChildren[name];
            var nextChild = nextChildren[name];
            if (prevChild === nextChild) {
              updates = enqueue(updates, this.moveChild(prevChild, lastPlacedNode, nextIndex, lastIndex));
              lastIndex = Math.max(prevChild._mountIndex, lastIndex);
              prevChild._mountIndex = nextIndex;
            } else {
              if (prevChild) {
                lastIndex = Math.max(prevChild._mountIndex, lastIndex);
              }
              updates = enqueue(updates, this._mountChildAtIndex(nextChild, lastPlacedNode, nextIndex, transaction, context));
            }
            nextIndex  ;
            lastPlacedNode = ReactReconciler.getNativeNode(nextChild);
          }
          for (name in removedNodes) {
            if (removedNodes.hasOwnProperty(name)) {
              updates = enqueue(updates, this._unmountChild(prevChildren[name], removedNodes[name]));
            }
          }
          if (updates) {
            processQueue(this, updates);
          }
          this._renderedChildren = nextChildren;
        }
    

    《深入React技术栈》这本书对Diff算法的解释比较好。其实只要记住几个原则以及在具体的计算updates队列的时候的算法优化的点就好了。

    传统的diff算法的复杂度是O(n^3),想要具体的了解可以去看"A Survey on Tree Edit Distance and Related Problems"

    这种复杂度在实际中应用会爆炸的,虽然现在的电脑的CPU很强,但一个页面也不能这样任性~。

    对此React的做法是给出合理的假设和方法来让整个diff过程合理简化。

    • DOM节点跨层级的移动操作的场景是很少见的,可以忽略不计。(合理,可以通过组件的设计来尽量保证DOM结构的稳定,必要时可以通过CSS的方法来进行DOM在展示上的调整,因为创建、删除以及移动DOM的操作是能少则少,浏览器的每个DOM节点都是一个大对象,有着很多的方法和属性
    • 同一类的两个组件将会生成相似的树形结构,不同类的两个组件将会生成不同的树形结构。(合理,本身组件就有提高页面的可复用性的作用,也就是将结构功能类似的页面结构(或者说相似的DOM树形结构)抽象成一类组件,所以合理的组件抽象就应该满足这条假设)
    • 对于同一层级的一组节点可以通过设置唯一的key来进行区分,从而做到diff的进一步优化。(这个不算是一个假设而是一个提高性能的方法)
    • 对于同一类的两个组件,有可能其Virtual Dom是没有任何变化的。因此React允许开发者通过shouldComponentUpdate()来判断组件是否需要进行diff算法分析。(合理,开发者本身对页面的理解来进一步进行diff的优化,当然这有可能会因为开发者错误的使用shouldComponentUpdate()判断错误了是否需要更新,从而得到了错误的结果.....但是这怪sei ???,写bug了还不老实)

    基于上面的几条,在具体的Diff过程中React只进行分层比较,新旧的树之间只比较同一个层次的节点。节点的操作分为3种:插入、移动和删除。

    节点移动操作判断的过程,引用《深入React技术栈》中的话:

    首先对新集合的节点进行循环遍历,for (name in nextChildren),通过唯一 key 可以判断新老集合中是否存在相同的节点,if (prevChild === nextChild),如果存在相同节点,则进行移动操作,但在移动前需要将当前节点在老集合中的位置与 lastIndex 进行比较,if (child._mountIndex < lastIndex),则进行节点移动操作,否则不执行该操作。这是一种顺序优化手段,lastIndex 一直在更新,表示访问过的节点在老集合中最右的位置(即最大的位置),如果新集合中当前访问的节点比 lastIndex 大,说明当前访问节点在老集合中就比上一个节点位置靠后,则该节点不会影响其他节点的位置,因此不用添加到差异队列中,即不执行移动操作,只有当访问的节点比 lastIndex 小时,才需要进行移动操作。

    需要注意的是”这是一种顺序优化手段,lastIndex 一直在更新,表示访问过的节点在老集合中最右的位置(即最大的位置),如果新集合中当前访问的节点比 lastIndex 大,说明当前访问节点在老集合中就比上一个节点位置靠后,则该节点不会影响其他节点的位置,因此不用添加到差异队列中,即不执行移动操作“这句话。意思是如果一个节点在旧集合中的位置已经在你之前进行判断的最后一个节点的背后,那么这个节点已经在被diff过的节点的后面了和之前的diff过的节点在顺序上就已经是正确的了,不需要移动了,反之的节点需要被移动。

    另外需要知道的是如果没有给key赋值,React会默认使用的是遍历过程中的 index 值。这里的index值指的是节点遍历的顺序号,效果等同于有些小伙伴用列表数组的index来当做key。这样其实是不好的,因为节点的key和节点的位置有关系和节点本身没关系,也就是如果我一个列表有10个节点,按照遍历的顺序key为1到10,然后我在列表的最开始增加了一个节点,这个时候按照列表遍历的顺序来设置key,则原来的10个节点的key都变了,而且新旧节点的key错误的对上了,要知道key在React中时对一个组件的身份识别的标示,错误或者重复的key会造成React错误的结果......so.......key需要是一个和节点本身有联系的唯一标示。

    react的作者之一Paul O’Shannessy有提到:

    Key is not really about performance, it’s more about identity (which in turn leads to better performance). Randomly assigned and changing values do not form an identity

    你可能会问,上面的diff算法的源码部分没看到key啊,恩,其实每个component的key会变成nextChildren&prevChildren对象中的name对应的value是component,另外在_reconcilerUpdateChildren中的shouldUpdateReactComponent组件的key也有使用到。

    对于新增和删除节点的操作简单来说:

    • 新增节点就是创建新的节点放在顺序遍历到的位置上。
    • 删除节点则是在该层次遍历结束后,对旧集合进行循环遍历,判断是否在新集合中没有,没有的话,则删除节点。

    当然上面说的移动、新增和删除节点的操作,不是马上执行的,而是收集到updates数组中,然后用processUpdates方法一次性进行具体的DOM的的更新。

      processUpdates: function (parentNode, updates) {
        for (var k = 0; k < updates.length; k  ) {
          var update = updates[k];
          switch (update.type) {
            case ReactMultiChildUpdateTypes.INSERT_MARKUP:
              insertLazyTreeChildAt(parentNode, update.content, getNodeAfter(parentNode, update.afterNode));
              break;
            case ReactMultiChildUpdateTypes.MOVE_EXISTING:
              moveChild(parentNode, update.fromNode, getNodeAfter(parentNode, update.afterNode));
              break;
            case ReactMultiChildUpdateTypes.SET_MARKUP:
              setInnerHTML(parentNode, update.content);
              break;
            case ReactMultiChildUpdateTypes.TEXT_CONTENT:
              setTextContent(parentNode, update.content);
              break;
            case ReactMultiChildUpdateTypes.REMOVE_NODE:
              removeChild(parentNode, update.fromNode);
              break;
          }
        }
      }
    

    其中的节点的具体的操作就是到具体的浏览器的DOM的节点的操作了,举个栗子。

    function insertLazyTreeChildAt(parentNode, childTree, referenceNode) {
      DOMLazyTree.insertTreeBefore(parentNode, childTree, referenceNode);
    }
    
    var insertTreeBefore = createMicrosoftUnsafeLocalFunction(function (parentNode, tree, referenceNode) {
      if (tree.node.nodeType === 11) {
        insertTreeChildren(tree);
        parentNode.insertBefore(tree.node, referenceNode);
      } else {
        parentNode.insertBefore(tree.node, referenceNode);
        insertTreeChildren(tree);
      }
    });
    

    Node.insertBefore()就是浏览器DOM操作的API了。

    想要跟着具体的Diff的过程来理解的话,推荐单步调试或者看《深入React技术栈》中的栗子,这里我就不画了.....画图很累的.....网上也非常多类似的搜一下就好了。

    本文对key的具体的使用的部分有待进一步深入。【TBD】

    参考资料:


    更多专业前端知识,请上【猿2048】www.mk2048.com
    展开全文
  • 目前,前端领域中 React...React diff 作为 Virtual DOM 的加速器,其算法上的改进优化是 React 整个界面渲染的基础,以及性能提高的保障,同时也是 React 源码中最神秘、最不可思议的部分,本文从源码入手,深入剖析 R

    目前,前端领域中 React 势头正盛,使用者众多却少有能够深入剖析内部实现机制和原理。本系列文章希望通过剖析 React 源码,理解其内部的实现原理,知其然更要知其所以然。

    React diff 作为 Virtual DOM 的加速器,其算法上的改进优化是 React 整个界面渲染的基础,以及性能提高的保障,同时也是 React 源码中最神秘、最不可思议的部分,本文从源码入手,深入剖析 React diff 的不可思议之处。

    • 阅读本文需要对 React 有一定的了解,如果你不知何为 React,请详读 React 官方文档

    • 如果你对 React diff 存在些许疑惑,或者你对算法优化感兴趣,那么本文值得阅读和讨论。

    前言

    React 中最值得称道的部分莫过于 Virtual DOM 与 diff 的完美结合,特别是其高效的 diff 算法,让用户可以无需顾忌性能问题而”任性自由”的刷新页面,让开发者也可以无需关心 Virtual DOM 背后的运作原理,因为 React diff 会帮助我们计算出 Virtual DOM 中真正变化的部分,并只针对该部分进行实际 DOM 操作,而非重新渲染整个页面,从而保证了每次操作更新后页面的高效渲染,因此 Virtual DOM 与 diff 是保证 React 性能口碑的幕后推手。

    行文至此,可能会有读者质疑:React 无非就是引入 diff 这一概念,且 diff 算法也并非其首创,何必吹嘘的如此天花乱坠呢?

    其实,正是因为 diff 算法的普识度高,就更应该认可 React 针对 diff 算法优化所做的努力与贡献,更能体现 React 开发者们的魅力与智慧!

    传统 diff 算法

    计算一棵树形结构转换成另一棵树形结构的最少操作,是一个复杂且值得研究的问题。传统 diff 算法通过循环递归对节点进行依次对比,效率低下,算法复杂度达到 O(n3),其中 n 是树中节点的总数。O(n3) 到底有多可怕,这意味着如果要展示1000个节点,就要依次执行上十亿次的比较。这种指数型的性能消耗对于前端渲染场景来说代价太高了!现今的 CPU 每秒钟能执行大约30亿条指令,即便是最高效的实现,也不可能在一秒内计算出差异情况。

    因此,如果 React 只是单纯的引入 diff 算法而没有任何的优化改进,那么其效率是远远无法满足前端渲染所要求的性能。

    通过下面的 demo 可以清晰的描述传统 diff 算法的实现过程。

    let result = [];
    // 比较叶子节点
    const diffLeafs = function(beforeLeaf, afterLeaf) {
      // 获取较大节点树的长度
      let count = Math.max(beforeLeaf.children.length, afterLeaf.children.length);
      // 循环遍历
      for (let i = 0; i < count; i++) {
        const beforeTag = beforeLeaf.children[i];
        const afterTag = afterLeaf.children[i];
        // 添加 afterTag 节点
        if (beforeTag === undefined) {
          result.push({type: "add", element: afterTag});
        // 删除 beforeTag 节点
        } else if (afterTag === undefined) {
          result.push({type: "remove", element: beforeTag});
        // 节点名改变时,删除 beforeTag 节点,添加 afterTag 节点
        } else if (beforeTag.tagName !== afterTag.tagName) {
          result.push({type: "remove", element: beforeTag});
          result.push({type: "add", element: afterTag});
        // 节点不变而内容改变时,改变节点
        } else if (beforeTag.innerHTML !== afterTag.innerHTML) {
          if (beforeTag.children.length === 0) {
            result.push({
              type: "changed",
              beforeElement: beforeTag,
              afterElement: afterTag,
              html: afterTag.innerHTML
          });
          } else {
            // 递归比较
            diffLeafs(beforeTag, afterTag);
          }
        }
      }
      return result;
    }

    因此,如果想要将 diff 思想引入 Virtual DOM,就需要设计一种稳定高效的 diff 算法,而 React 做到了!

    那么,React diff 到底是如何实现的呢?

    详解 React diff

    传统 diff 算法的复杂度为 O(n3),显然这是无法满足性能要求的。React 通过制定大胆的策略,将 O(n3) 复杂度的问题转换成 O(n) 复杂度的问题

    diff 策略

    1. Web UI 中 DOM 节点跨层级的移动操作特别少,可以忽略不计。
    2. 拥有相同类的两个组件将会生成相似的树形结构,拥有不同类的两个组件将会生成不同的树形结构。
    3. 对于同一层级的一组子节点,它们可以通过唯一 id 进行区分。

    基于以上三个前提策略,React 分别对 tree diff、component diff 以及 element diff 进行算法优化,事实也证明这三个前提策略是合理且准确的,它保证了整体界面构建的性能。

    • tree diff
    • component diff
    • element diff

    本文中源码 ReactMultiChild.js

    tree diff

    基于策略一,React 对树的算法进行了简洁明了的优化,即对树进行分层比较,两棵树只会对同一层次的节点进行比较。

    既然 DOM 节点跨层级的移动操作少到可以忽略不计,针对这一现象,React 通过 updateDepth 对 Virtual DOM 树进行层级控制,只会对相同颜色方框内的 DOM 节点进行比较,即同一个父节点下的所有子节点。当发现节点已经不存在,则该节点及其子节点会被完全删除掉,不会用于进一步的比较。这样只需要对树进行一次遍历,便能完成整个 DOM 树的比较。

    updateChildren: function(nextNestedChildrenElements, transaction, context) {
      updateDepth++;
      var errorThrown = true;
      try {
        this._updateChildren(nextNestedChildrenElements, transaction, context);
        errorThrown = false;
      } finally {
        updateDepth--;
        if (!updateDepth) {
          if (errorThrown) {
            clearQueue();
          } else {
            processQueue();
          }
        }
      }
    }

    分析至此,大部分人可能都存在这样的疑问:如果出现了 DOM 节点跨层级的移动操作,React diff 会有怎样的表现呢?是的,对此我也好奇不已,不如试验一番。

    如下图,A 节点(包括其子节点)整个被移动到 D 节点下,由于 React 只会简单的考虑同层级节点的位置变换,而对于不同层级的节点,只有创建和删除操作。当根节点发现子节点中 A 消失了,就会直接销毁 A;当 D 发现多了一个子节点 A,则会创建新的 A(包括子节点)作为其子节点。此时,React diff 的执行情况:create A -> create B -> create C -> delete A

    由此可发现,当出现节点跨层级移动时,并不会出现想象中的移动操作,而是以 A 为根节点的树被整个重新创建,这是一种影响 React 性能的操作,因此 React 官方建议不要进行 DOM 节点跨层级的操作

    注意:在开发组件时,保持稳定的 DOM 结构会有助于性能的提升。例如,可以通过 CSS 隐藏或显示节点,而不是真的移除或添加 DOM 节点。

    DOM层级变换

    component diff

    React 是基于组件构建应用的,对于组件间的比较所采取的策略也是简洁高效。

    • 如果是同一类型的组件,按照原策略继续比较 virtual DOM tree。

    • 如果不是,则将该组件判断为 dirty component,从而替换整个组件下的所有子节点。

    • 对于同一类型的组件,有可能其 Virtual DOM 没有任何变化,如果能够确切的知道这点那可以节省大量的 diff 运算时间,因此 React 允许用户通过 shouldComponentUpdate() 来判断该组件是否需要进行 diff。

    如下图,当 component D 改变为 component G 时,即使这两个 component 结构相似,一旦 React 判断 D 和 G 是不同类型的组件,就不会比较二者的结构,而是直接删除 component D,重新创建 component G 以及其子节点。虽然当两个 component 是不同类型但结构相似时,React diff 会影响性能,但正如 React 官方博客所言:不同类型的 component 是很少存在相似 DOM tree 的机会,因此这种极端因素很难在实现开发过程中造成重大影响的。

    component diff

    element diff

    当节点处于同一层级时,React diff 提供了三种节点操作,分别为:INSERT_MARKUP(插入)、MOVE_EXISTING(移动)和 REMOVE_NODE(删除)。

    • INSERT_MARKUP,新的 component 类型不在老集合里, 即是全新的节点,需要对新节点执行插入操作。

    • MOVE_EXISTING,在老集合有新 component 类型,且 element 是可更新的类型,generateComponentChildren 已调用 receiveComponent,这种情况下 prevChild=nextChild,就需要做移动操作,可以复用以前的 DOM 节点。

    • REMOVE_NODE,老 component 类型,在新集合里也有,但对应的 element 不同则不能直接复用和更新,需要执行删除操作,或者老 component 不在新集合里的,也需要执行删除操作。

    function enqueueInsertMarkup(parentInst, markup, toIndex) {
      updateQueue.push({
        parentInst: parentInst,
        parentNode: null,
        type: ReactMultiChildUpdateTypes.INSERT_MARKUP,
        markupIndex: markupQueue.push(markup) - 1,
        content: null,
        fromIndex: null,
        toIndex: toIndex,
      });
    }
    
    function enqueueMove(parentInst, fromIndex, toIndex) {
      updateQueue.push({
        parentInst: parentInst,
        parentNode: null,
        type: ReactMultiChildUpdateTypes.MOVE_EXISTING,
        markupIndex: null,
        content: null,
        fromIndex: fromIndex,
        toIndex: toIndex,
      });
    }
    
    function enqueueRemove(parentInst, fromIndex) {
      updateQueue.push({
        parentInst: parentInst,
        parentNode: null,
        type: ReactMultiChildUpdateTypes.REMOVE_NODE,
        markupIndex: null,
        content: null,
        fromIndex: fromIndex,
        toIndex: null,
      });
    }

    如下图,老集合中包含节点:A、B、C、D,更新后的新集合中包含节点:B、A、D、C,此时新老集合进行 diff 差异化对比,发现 B != A,则创建并插入 B 至新集合,删除老集合 A;以此类推,创建并插入 A、D 和 C,删除 B、C 和 D。

    no key

    React 发现这类操作繁琐冗余,因为这些都是相同的节点,但由于位置发生变化,导致需要进行繁杂低效的删除、创建操作,其实只要对这些节点进行位置移动即可。

    针对这一现象,React 提出优化策略:允许开发者对同一层级的同组子节点,添加唯一 key 进行区分,虽然只是小小的改动,性能上却发生了翻天覆地的变化!

    新老集合所包含的节点,如下图所示,新老集合进行 diff 差异化对比,通过 key 发现新老集合中的节点都是相同的节点,因此无需进行节点删除和创建,只需要将老集合中节点的位置进行移动,更新为新集合中节点的位置,此时 React 给出的 diff 结果为:B、D 不做任何操作,A、C 进行移动操作,即可。

    add key

    那么,如此高效的 diff 到底是如何运作的呢?让我们通过源码进行详细分析。

    首先对新集合的节点进行循环遍历,for (name in nextChildren),通过唯一 key 可以判断新老集合中是否存在相同的节点,if (prevChild === nextChild),如果存在相同节点,则进行移动操作,但在移动前需要将当前节点在老集合中的位置与 lastIndex 进行比较,if (child._mountIndex < lastIndex),则进行节点移动操作,否则不执行该操作。这是一种顺序优化手段,lastIndex 一直在更新,表示访问过的节点在老集合中最右的位置(即最大的位置),如果新集合中当前访问的节点比 lastIndex 大,说明当前访问节点在老集合中就比上一个节点位置靠后,则该节点不会影响其他节点的位置,因此不用添加到差异队列中,即不执行移动操作,只有当访问的节点比 lastIndex 小时,才需要进行移动操作。

    以上图为例,可以更为清晰直观的描述 diff 的差异对比过程:

    • 从新集合中取得 B,判断老集合中存在相同节点 B,通过对比节点位置判断是否进行移动操作,B 在老集合中的位置 B._mountIndex = 1,此时 lastIndex = 0,不满足 child._mountIndex < lastIndex 的条件,因此不对 B 进行移动操作;更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex),其中 prevChild._mountIndex 表示 B 在老集合中的位置,则 lastIndex = 1,并将 B 的位置更新为新集合中的位置 prevChild._mountIndex = nextIndex,此时新集合中 B._mountIndex = 0nextIndex++ 进入下一个节点的判断。

    • 从新集合中取得 A,判断老集合中存在相同节点 A,通过对比节点位置判断是否进行移动操作,A 在老集合中的位置 A._mountIndex = 0,此时 lastIndex = 1,满足 child._mountIndex < lastIndex的条件,因此对 A 进行移动操作enqueueMove(this, child._mountIndex, toIndex),其中 toIndex 其实就是 nextIndex,表示 A 需要移动到的位置;更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex),则 lastIndex = 1,并将 A 的位置更新为新集合中的位置 prevChild._mountIndex = nextIndex,此时新集合中 A._mountIndex = 1nextIndex++ 进入下一个节点的判断。

    • 从新集合中取得 D,判断老集合中存在相同节点 D,通过对比节点位置判断是否进行移动操作,D 在老集合中的位置 D._mountIndex = 3,此时 lastIndex = 1,不满足 child._mountIndex < lastIndex的条件,因此不对 D 进行移动操作;更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex),则 lastIndex = 3,并将 D 的位置更新为新集合中的位置 prevChild._mountIndex = nextIndex,此时新集合中 D._mountIndex = 2nextIndex++ 进入下一个节点的判断。

    • 从新集合中取得 C,判断老集合中存在相同节点 C,通过对比节点位置判断是否进行移动操作,C 在老集合中的位置 C._mountIndex = 2,此时 lastIndex = 3,满足 child._mountIndex < lastIndex 的条件,因此对 C 进行移动操作 enqueueMove(this, child._mountIndex, toIndex);更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex),则 lastIndex = 3,并将 C 的位置更新为新集合中的位置 prevChild._mountIndex = nextIndex,此时新集合中 A._mountIndex = 3nextIndex++ 进入下一个节点的判断,由于 C 已经是最后一个节点,因此 diff 到此完成。

    以上主要分析新老集合中存在相同节点但位置不同时,对节点进行位置移动的情况,如果新集合中有新加入的节点且老集合存在需要删除的节点,那么 React diff 又是如何对比运作的呢?

    以下图为例:

    • 从新集合中取得 B,判断老集合中存在相同节点 B,由于 B 在老集合中的位置 B._mountIndex = 1,此时 lastIndex = 0,因此不对 B 进行移动操作;更新 lastIndex = 1,并将 B 的位置更新为新集合中的位置 B._mountIndex = 0nextIndex++进入下一个节点的判断。

    • 从新集合中取得 E,判断老集合中不存在相同节点 E,则创建新节点 E;更新 lastIndex = 1,并将 E 的位置更新为新集合中的位置,nextIndex++进入下一个节点的判断。

    • 从新集合中取得 C,判断老集合中存在相同节点 C,由于 C 在老集合中的位置C._mountIndex = 2,此时 lastIndex = 1,因此对 C 进行移动操作;更新 lastIndex = 2,并将 C 的位置更新为新集合中的位置,nextIndex++ 进入下一个节点的判断。

    • 从新集合中取得 A,判断老集合中存在相同节点 A,由于 A 在老集合中的位置A._mountIndex = 0,此时 lastIndex = 2,因此不对 A 进行移动操作;更新 lastIndex = 2,并将 A 的位置更新为新集合中的位置,nextIndex++进入下一个节点的判断。

    • 当完成新集合中所有节点 diff 时,最后还需要对老集合进行循环遍历,判断是否存在新集合中没有但老集合中仍存在的节点,发现存在这样的节点 D,因此删除节点 D,到此 diff 全部完成。

    创建移动删除节点

    _updateChildren: function(nextNestedChildrenElements, transaction, context) {
      var prevChildren = this._renderedChildren;
      var nextChildren = this._reconcilerUpdateChildren(
        prevChildren, nextNestedChildrenElements, transaction, context
      );
      if (!nextChildren && !prevChildren) {
        return;
      }
      var name;
      var lastIndex = 0;
      var nextIndex = 0;
      for (name in nextChildren) {
        if (!nextChildren.hasOwnProperty(name)) {
          continue;
        }
        var prevChild = prevChildren && prevChildren[name];
        var nextChild = nextChildren[name];
        if (prevChild === nextChild) {
          // 移动节点
          this.moveChild(prevChild, nextIndex, lastIndex);
          lastIndex = Math.max(prevChild._mountIndex, lastIndex);
          prevChild._mountIndex = nextIndex;
        } else {
          if (prevChild) {
            lastIndex = Math.max(prevChild._mountIndex, lastIndex);
            // 删除节点
            this._unmountChild(prevChild);
          }
          // 初始化并创建节点
          this._mountChildAtIndex(
            nextChild, nextIndex, transaction, context
          );
        }
        nextIndex++;
      }
      for (name in prevChildren) {
        if (prevChildren.hasOwnProperty(name) &&
            !(nextChildren && nextChildren.hasOwnProperty(name))) {
          this._unmountChild(prevChildren[name]);
        }
      }
      this._renderedChildren = nextChildren;
    },
    // 移动节点
    moveChild: function(child, toIndex, lastIndex) {
      if (child._mountIndex < lastIndex) {
        this.prepareToManageChildren();
        enqueueMove(this, child._mountIndex, toIndex);
      }
    },
    // 创建节点
    createChild: function(child, mountImage) {
      this.prepareToManageChildren();
      enqueueInsertMarkup(this, mountImage, child._mountIndex);
    },
    // 删除节点
    removeChild: function(child) {
      this.prepareToManageChildren();
      enqueueRemove(this, child._mountIndex);
    },
    
    _unmountChild: function(child) {
      this.removeChild(child);
      child._mountIndex = null;
    },
    
    _mountChildAtIndex: function(
      child,
      index,
      transaction,
      context) {
      var mountImage = ReactReconciler.mountComponent(
        child,
        transaction,
        this,
        this._nativeContainerInfo,
        context
      );
      child._mountIndex = index;
      this.createChild(child, mountImage);
    },

    当然,React diff 还是存在些许不足与待优化的地方,如下图所示,若新集合的节点更新为:D、A、B、C,与老集合对比只有 D 节点移动,而 A、B、C 仍然保持原有的顺序,理论上 diff 应该只需对 D 执行移动操作,然而由于 D 在老集合的位置是最大的,导致其他节点的 _mountIndex < lastIndex,造成 D 没有执行移动操作,而是 A、B、C 全部移动到 D 节点后面的现象。

    在此,读者们可以讨论思考:如何优化上述问题?

    建议:在开发过程中,尽量减少类似将最后一个节点移动到列表首部的操作,当节点数量过大或更新操作过于频繁时,在一定程度上会影响 React 的渲染性能。

    key last

    总结

    • React 通过制定大胆的 diff 策略,将 O(n3) 复杂度的问题转换成 O(n) 复杂度的问题;

    • React 通过分层求异的策略,对 tree diff 进行算法优化;

    • React 通过相同类生成相似树形结构,不同类生成不同树形结构的策略,对 component diff 进行算法优化;

    • React 通过设置唯一 key的策略,对 element diff 进行算法优化;

    • 建议,在开发组件时,保持稳定的 DOM 结构会有助于性能的提升;

    • 建议,在开发过程中,尽量减少类似将最后一个节点移动到列表首部的操作,当节点数量过大或更新操作过于频繁时,在一定程度上会影响 React 的渲染性能。

    参考资料

    展开全文
  • diff作为VirtualDOM的加速器,其算法上的改进优化是React整个界面渲染的基础和性能的保障。diff会帮助我们就散出VirtualDOM中真正变化的部分,并只针对该部分进行原生DOM操作,而不是渲染整个页面。从而保证了每次...

    diff作为VirtualDOM的加速器,其算法上的改进优化是React整个界面渲染的基础和性能的保障。

    diff会帮助我们就散出VirtualDOM中真正变化的部分,并只针对该部分进行原生DOM操作,而不是渲染整个页面。从而保证了每次操作更新后页面的高效渲染。

    传统的diff算法

    计算一颗树形结构转换成另一颗树形结构的最少操作,是一个很复杂的问题。传统diff算法通过循环递归对节点进行依次对比,效率低下。复杂度可达到O(n^3)。

    React改进了diff算法,新的diff算法更加稳定、高效。

    React diff算法详解

    React将VirtualDOM树转换为actualDOM的最少操作过程称为调和(reconciliation)。

    diff算法就是调和过程的具体实现。

    1、diff策略

    策略1: DOM节点跨层级的移动操作很少,忽略不计。
    策略2: 拥有相同类的两个组件将会生成相似的树形结构,拥有不同类的两个组件将会生成不同的树形结构。
    策略3: 对于同一个层级的一组子节点,可以通过它们唯一的ID来区分。

    2、tree diff

    基于策略1,React对树的算法进行了简洁明了的优化:只对树进行分层比较,两棵树只会对同一层次的节点进行比较。

    React只会对相同层级的DOM节点进行比较,即同一个父节点下的所有子节点,当发现该节点已经不存在了,就会删除该节点和其所有子节点,不会再做进一步的比较。

    而如果真的出现了跨层级的移动,并不会出现移动操作,而是被移动的跟节点被删除而后重新创建。

    3、component diff

    组件之间的比较策略:
    1、如果是同一类型的组件,按原策略继续比较VirtualDOM树即可
    2、如果不是,则将该组件判断为dirty component,从而替换整个组件下的所有子节点。
    3、对于同一类型的组件,可能其virtualDOM没有任何变化,如果能确切的知道这一点,那么就可以节省大量的diff运算时间。因此,React允许用户通过shouldComponentUpdate()来判断是否需要对组件进行diff算法分析。

    4、element diff

    当节点处于同一个层级的时候,diff提供了三种节点操作:INSERT_MARKUP(插入)、MOVE_EXISTING(移动)、REMOVE_NODE(删除)。
    1、插入:新的组件不在旧的集合里,也就是是一个全新的节点。
    2、旧集合中有新的组件类型,且element是可更新的类型,generateComponent-Children已经调用receiveComponent,这种情况下prevChild=nextChild,就需要做移动操作,可以复用以前的DOM节点。
    3、旧组件类型,在新集合里也有,但对应的element不同则不能直接复用和更新,需要执行删除操作。或者旧组件不在新集合里,也要执行删除操作。

    展开全文
  • 没时间详细写 都写在注释里面了,有空细说 diff.js zzvar _ = require('./util') ...var listDiff = require('list-diff2') function diff (oldTree, newTree) { var index = 0 var patches = {} ...

    没时间详细写 都写在注释里面了,有空细说

    diff.js

    zzvar _ = require('./util')
    var patch = require('./patch')
    var listDiff = require('list-diff2')
    
    function diff (oldTree, newTree) {
      var index = 0
      var patches = {}
      dfsWalk(oldTree, newTree, index, patches)
      return patches
    }
    
    function dfsWalk (oldNode, newNode, index, patches) {
      var currentPatch = []
    
      // 节点被移除Node is removed.
      if (newNode === null) {
      // Real DOM node will be removed when perform reordering, 
      // so has no needs to do anthings in here
      
      //节点为文本 内容改变TextNode content replacing
      } else if (_.isString(oldNode) && _.isString(newNode)) {
        if (newNode !== oldNode) {
          currentPatch.push({ type: patch.TEXT, content: newNode })
        }
    
      //节点类型相同 遍历属性和孩子
      // Nodes are the same, diff old node's props and children
      } else if (
          oldNode.tagName === newNode.tagName &&
          oldNode.key === newNode.key
        ) {
    
        // Diff props 遍历属性
        var propsPatches = diffProps(oldNode, newNode)
        if (propsPatches) {
          currentPatch.push({ type: patch.PROPS, props: propsPatches })
        }
    
        // Diff children. If the node has a `ignore` property, do not diff children
        // 遍历孩子
        if (!isIgnoreChildren(newNode)) {
          diffChildren(
            oldNode.children,
            newNode.children,
            index,
            patches,
            currentPatch
          )
        }
    
      // 节点类型不同 新节点直接替换旧节点Nodes are not the same, replace the old node with new node
      } else {
        currentPatch.push({ type: patch.REPLACE, node: newNode })
      }
    
      //index是每个节点都有的一个索引 每个!
      if (currentPatch.length) {
        patches[index] = currentPatch
      }
    }
    
    //为什么这里要把子节点的递归单独写出来 而不直接写在dfswalk函数里面呢?
    //我认为其实非要写也是可以写进dfswalk里面的,但是为了功能分离、解耦所以单独提出来写
    function diffChildren (oldChildren, newChildren, index, patches, currentPatch) {
      //该key就指的是循环绑定上的key值
      var diffs = listDiff(oldChildren, newChildren, 'key')
      newChildren = diffs.children
    
      if (diffs.moves.length) {
        var reorderPatch = { type: patch.REORDER, moves: diffs.moves }
        currentPatch.push(reorderPatch)
      }
    
      var leftNode = null
      var currentNodeIndex = index
      _.each(oldChildren, function (child, i) {
        var newChild = newChildren[i]
        currentNodeIndex = (leftNode && leftNode.count)
        //index当前的节点的标志。因为在深度优先遍历的过程中,每个节点都有一个index
        //count为子节点个数
        //为什么这里是+leftNode.count, 因为每次diffChildren是遍历该节点的子节点按照顺序来
        //自己的第一个子节点是自己的index再加上和左边节点的子节点数也就是leftNode.index
        //第一次进diffchildren函数肯定是第一个节点,不存在有左边的节点,所以...
          ? currentNodeIndex + leftNode.count + 1
        //
          : currentNodeIndex + 1
        dfsWalk(child, newChild, currentNodeIndex, patches)
        leftNode = child
      })
    }
    
    function diffProps (oldNode, newNode) {
      var count = 0
      var oldProps = oldNode.props
      var newProps = newNode.props
    
      var key, value
      var propsPatches = {}
    
      // Find out different properties
      for (key in oldProps) {
        value = oldProps[key]
        if (newProps[key] !== value) {
          count++
          propsPatches[key] = newProps[key]
        }
      }
    
      // Find out new property
      for (key in newProps) {
        value = newProps[key]
        if (!oldProps.hasOwnProperty(key)) {
          count++
          propsPatches[key] = newProps[key]
        }
      }
      // If properties all are identical
      if (count === 0) {
        return null
      }
      return propsPatches
    }
    
    
    
    function isIgnoreChildren (node) {
      return (node.props && node.props.hasOwnProperty('ignore'))
    }
    
    module.exports = diff
    

    list-diff.js 用于比对同一层的节点

    /**
     * Diff two list in O(N).
     * @param {Array} oldList - Original List
     * @param {Array} newList - List After certain insertions, removes, or moves
     * @return {Object} - {moves: <Array>}
     *                  - moves is a list of actions that telling how to remove and insert
     */
    function diff (oldList, newList, key) {
      var oldMap = makeKeyIndexAndFree(oldList, key)
      var newMap = makeKeyIndexAndFree(newList, key)
    
      var newFree = newMap.free
    
      //oldKeyIndex和newKeyIndex是以节点为key,index为值的一个对象
      var oldKeyIndex = oldMap.keyIndex
      var newKeyIndex = newMap.keyIndex
    
      var moves = []
    
      // a simulate list to manipulate
      var children = []
      var i = 0
      var item
      var itemKey
      var freeIndex = 0
    
      // first pass to check item in old list: if it's removed or not
      while (i < oldList.length) {
        item = oldList[i]
        itemKey = getItemKey(item, key)
        if (itemKey) {
          //如果该旧节点的key值 在新节点中不存在 push null
          if (!newKeyIndex.hasOwnProperty(itemKey)) {
            children.push(null)
          //如果存在,则把该节点push进children数组
          } else {
            var newItemIndex = newKeyIndex[itemKey]
            children.push(newList[newItemIndex])
          }
        //如果旧节点本身不存在,判断新节点中是不是也不存在?
        } else {
          var freeItem = newFree[freeIndex++]
          children.push(freeItem || null)
        }
        i++
      }
    
      //simulateList里面是旧树和新树里面都存在的节点,新树单独有的新节点并不在里面
      var simulateList = children.slice(0)
    
      //移除不存在的节点
      // remove items no longer exist
      i = 0
      while (i < simulateList.length) {
        if (simulateList[i] === null) {
          remove(i)
          removeSimulate(i)
        } else {
          i++
        }
      }
    
      // i is cursor pointing to a item in new list
      // j is cursor pointing to a item in simulateList
      var j = i = 0
      while (i < newList.length) {
        item = newList[i]
        itemKey = getItemKey(item, key)
    
        var simulateItem = simulateList[j]
        var simulateItemKey = getItemKey(simulateItem, key)
    
        if (simulateItem) {
          //新树中的此节点不为新增节点(依据:同一位置的key是否相同,即simulateItemKey和itemkey是否一致)
          //两者key相同,说明该节点位置没有改动
          if (itemKey === simulateItemKey) {
            j++
    
          //此位置节点的key与同位置的simulateList中的节点的key不一致
          //判断是新增节点(依据:旧树中是否有此节点)还是只是移位了
          } 
          else {
            //情况1:旧树中没有此节点,为新增节点,直接插入一个新节点
            // new item, just inesrt it
            if (!oldKeyIndex.hasOwnProperty(itemKey)) {
              insert(i, item)
            } 
    
            //情况2:旧树中有此节点,说明只是节点移动了位置
            else {
              //if remove current simulateItem make item in right place
              //then just remove it
              //情况2.1当前节点移动被移动
              //simulateList[1,2,3,4,5] newList[2,3,4,5,1]
              var nextItemKey = getItemKey(simulateList[j + 1], key)
              if (nextItemKey === itemKey) {
                remove(i)
                removeSimulate(j)
                j++ // after removing, current j is right, just jump to next one
              } 
            
              else {
                // else insert item
                // 情况2.2当前及之后的多个节点被移动 or 后面的节点移动到了前面
                // simulateList[1,2,3,4,5] newList[3,4,5,1,2]
                // or simulateList[1,2,3,4,5] newList[5,1,2,3,4]
                insert(i, item)
              }
            }
          }
        } 
        //已经遍历完simulateList了(j>=simulateList.length),如果i还未遍历完newList
        //只能说明在新树末尾增加了一个新节点 直接insert
        else {
          insert(i, item)
        }
    
        i++
      }
    
      //if j is not remove to the end, remove all the rest item
      //如果j没有遍历完simulateList,遍历删除剩下的item
      var k = simulateList.length - j
      while (j++ < simulateList.length) {
        k--
        remove(k + i)
      }
    
    
      function remove (index) {
        var move = {index: index, type: 0}
        moves.push(move)
      }
    
      function insert (index, item) {
        var move = {index: index, item: item, type: 1}
        moves.push(move)
      }
    
      function removeSimulate (index) {
        simulateList.splice(index, 1)
      }
    
      return {
        moves: moves,
        children: children
      }
    }
    
    /**
     * Convert list to key-item keyIndex object.
     * @param {Array} list
     * @param {String|Function} key
     */
    function makeKeyIndexAndFree (list, key) {
      var keyIndex = {}
      var free = []
      for (var i = 0, len = list.length; i < len; i++) {
        var item = list[i]
        var itemKey = getItemKey(item, key)
        if (itemKey) {
          keyIndex[itemKey] = i
        } else {
          free.push(item)
        }
      }
      return {
        keyIndex: keyIndex,
        free: free
      }
    }
    
    //获取节点的key值
    function getItemKey (item, key) {
      //void 666 = undefined 666纯属开玩笑
      if (!item || !key) return void 666
      return typeof key === 'string'
        ? item[key]
        : key(item)
    }
    
    exports.makeKeyIndexAndFree = makeKeyIndexAndFree // exports for test
    exports.diff = diff
    

     

    展开全文
  • 著作权归作者所有。 商业转载请联系作者获得授权,非商业转载请注明出处。 作者:twobin ... 来源:知乎 ...本系列文章希望通过剖析 React 源码,理解其内部的实现原理,知其然更要知其所以然。 Rea
  • React源码结构树: 在这些目录结构中,renderers是React代码的核心部分,它包含了大部分功能的实现。renderers源码目录:在renderers中,reconciler(协调器)是最核心的部分,包含React中自定义组件的实现、组件...
  • 在前面我们实现了_render方法,就是把虚拟dom转换为真实的dom,下面我们需要优化一下这个方法,不要让它傻乎乎的渲染整个dom树,对比需要变化的地方,只渲染需要变化的地方,这样的过程,就是diff算法。 对比当前...
  • React源码分析1 -- 框架

    2017-03-02 16:33:14
    1 源码结构我们分析的React源码version为16.0.0-alpha.3,源码目录如下图所示。含义如下 addons:插件,一些比较有用的工具,如transition动画 isomorphic: 同构,服务端在页面初次加载时,将所有方法渲染好,一次性...
  • react diff算法浅析

    2017-09-26 22:07:00
    diff算法作为Virtual DOM的加速器,其算法的改进优化是React整个界面渲染的基础和性能的保障,同时也是React源码中最神秘的,最不可思议的部分1.传统diff算法计算一棵树形结构转换为另一棵树形结构需要最少步骤,...
  • 传统diff 计算两颗树形结构差异并进行转换,传统diff算法是这样做的:循环递归每一个节点 传统diff.png ...比如左侧树a节点依次进行如下对比,左侧树节点b、c、d、e...react优化的diff策略 传统diff算法复杂度达..
  • React源码Diff算法

    2019-04-03 12:23:51
    React框架使用的目的,就是为了维护状态,更新视图。 为什么会说传统DOM操作效率低呢?当使用document.createElement()创建了一个空的Element时,会需要按照标准实现一大堆的东西,如下图所示。此外,在对DOM进行...
  • 在看React源码之前,我一直认为React中的事件实现和原生的事件绑定差别不大,但是真正阅读源码后,发现和我最初的想法是大相径庭的:React采用合成事件,所谓的合成事件,简单来说就是React中的事件绑定是被React...
  • react源码分析

    2017-05-23 11:03:44
    原文地址:http://www.html-js.com/article/JS-analysis-of-the-single-row-from-zero-reactjs-source-first-rendering-principle%203154 前端的发展特别快,经历过jQuery一统天下的工具库时代后,现在各种框架又...
  • 无论是在 vue 还是 react 中,使用 key 都是一个 必须面对的问题,最近就对 react 的key 做了一点学习,这里就当做个人的学习笔记了 我们就来看这里的 (已删除 多余的代码,只留下了 数组类型的 子节点 ) // ...
  • 1 React生命周期流程调用流程可以参看上图。分为实例化,存在期和销毁三个不同阶段。介绍生命周期流程的文章很多,相信大部分同学也有所了解,我们就不详细分析了。很多同学肯定有疑问,这些方法在React内部是在哪些...
1 2 3 4 5 ... 20
收藏数 2,635
精华内容 1,054
热门标签
关键字:

diff react 源码