Virtual Dom Difference

Diff算法

为了尽可能减少DOM插入删除相关的操作，React提出了一套虚拟树差异处理算法。算法的主要流程如下图所示:

所有实际的DOM操作会存放到ChildDOMOperations的队列中，diff算法就是给每个子组件明确要执行的操作是什么，然后入队到操作队列中。

所有新的子元素集合成为nextChildren，已经渲染的子元素集合成为currentChildren。首先会通过key判断，nextChildren中的元素是否在currentChildren中存在，如果不存在，则挂载这个新的元素；如果存在，判断二者类型是否一致，不一致的话，也是先卸载掉当前子组件，挂载新的子组件，而两者类型一致时，只需要判断是否需要更新位置信息即可。

有的时候还会出现一种情况，就是currentChildren中出现过的元素，未必仍然会保留在nextChildren中，因此，还需要遍历一遍currentChildren，把没有出现在nextChildren中的元素都卸载掉。

DOMOperation

在Diff算法过程中，所有的DOM操作都会存放在一个队列中，等到最后再执行。DOMOperation有三种类型：insertMarkup，moveFrom和removeAt。相关的调用如下：

// src/core/ReactMultiChild.js
processChildDOMOperationsQueue: function() {
    if (this.domOperations) {
      ReactComponent.DOMIDOperations
        .manageChildrenByParentID(this._rootNodeID, this.domOperations);
      this.domOperations = null;
    }
}

// src/core/ReactDOMIDOperation.js 
manageChildrenByParentID: function(parentID, domOperations) {
    var parent = ReactDOMNodeCache.getCachedNodeByID(parentID);
    DOMChildrenOperations.manageChildren(parent, domOperations);
    ReactDOMNodeCache.purgeEntireCache();
}

// src/domUtils/DOMChildrenOperations.js
var manageChildren = function(parent, childOperations) {
  var nodesByOriginalIndex = _getNodesByOriginalIndex(parent, childOperations);
  if (nodesByOriginalIndex) {
    _removeChildrenByOriginalIndex(parent, nodesByOriginalIndex);
  }
  _placeNodesAtDestination(parent, childOperations, nodesByOriginalIndex);
};

React定义的函数非常好的体现了keep it simple的原则。可以看到，从processChildDOMOperationsQueue到manageChildrenByParentID，代码量并不多，但各自关注的内容不一样。 函数_getNodesByOriginalIndex会根据childOperations中moveFrom和removeAt的信息，将parent中相关的原始节点存储到数组中返回，由于这些节点都会被删除（moveFrom会被重新插入），因此如果nodesByOriginalIndex的节点不为空，就会调用_removeChildrenByOriginalIndex把它们都删除掉。

var _removeChildrenByOriginalIndex = function(parent, nodesByOriginalIndex) {
  for (var j = 0; j < nodesByOriginalIndex.length; j++) {
    var nodeToRemove = nodesByOriginalIndex[j];
    if (nodeToRemove) {     // We used a sparse array.
      parent.removeChild(nodesByOriginalIndex[j]);
    }
  }
};

删除后紧接着就要进行插入操作了，相关的方法被封装在了_placeNodesAtDestination中，它只处理moveFrom和insertMarkup两种类型的操作。

var _placeNodesAtDestination =
  function(parent, childOperations, nodesByOriginalIndex) {
    var origNode;
    var finalIndex;
    var lastFinalIndex = -1;
    var childOperation;
    for (var k = 0; k < childOperations.length; k++) {
      childOperation = childOperations[k];
      if (MOVE_NODE_AT_ORIG_INDEX in childOperation) {
        origNode = nodesByOriginalIndex[childOperation.moveFrom];
        finalIndex = childOperation.finalIndex;
        insertNodeAt(parent, origNode, finalIndex);
        if (__DEV__) {
          throwIf(finalIndex <= lastFinalIndex, NON_INCREASING_OPERATIONS);
          lastFinalIndex = finalIndex;
        }
      } else if (REMOVE_AT in childOperation) {
      } else if (INSERT_MARKUP in childOperation) {
        finalIndex = childOperation.finalIndex;
        var markup = childOperation.insertMarkup;
        Danger.dangerouslyInsertMarkupAt(parent, markup, finalIndex);
        if (__DEV__) {
          throwIf(finalIndex <= lastFinalIndex, NON_INCREASING_OPERATIONS);
          lastFinalIndex = finalIndex;
        }
      }
    }
  };

执行插入markup时，会调用到一个Danger.dangerouslyInsertMarkupAt的方法，这个方法的名称着实让人紧张，那么它到底做了什么呢？来看看它的实现。

function dangerouslyInsertMarkupAt(parentNode, markup, index) {
  if (__DEV__) {
    validateMarkupParams(parentNode, markup);
  }
  var parentDummy = getParentDummy(parentNode);
  parentDummy.innerHTML = markup;
  var htmlCollection = parentDummy.childNodes;
  var afterNode = index ? parentNode.childNodes[index - 1] : null;
  inefficientlyInsertHTMLCollectionAfter(parentNode, htmlCollection, afterNode);
}

开发模式下，还会对插入的markup进行校验，正是环境中，这一步就取消了。getParentDummy会返回一个标签类型相同的dummy对象，所有的dummy对象会被存储在dummies中，若dummies中不存在，就新建一个存放进去。 当dummy元素生成好之后，将其innerHTML更新为待插入的markup字符串，就完成了将字符串转化成DOM节点集合。

紧接着要做的，就是将这些DOM节点实际的插入到父节点中，在inefficientlyInsertHTMLToCollectionAfter中，就是通过逐一对DOM节点集合中的元素，调用inssertBefore或者appendChild方法，完成插入过程。

  for (var i = 0; i < originalLength; i++) {
    ret =
      insertNodeAfterNode(parentRootDomNode, htmlCollection[0], ret || after);
  }

NodeList动态集合

上面是执行插入的代码，细心的人可能看到了htmlCollection[0]，而不是htmlCollection[i]，这里真的不是打错了吗？的确不是，这里涉及到了一个NodeList的动态集合特性。

htmlCollection是一个NodeList类型，MDN上对NodeList类型的解释是：

Although NodeList is not an Array, it is possible to iterate on it using forEach(). Several older browsers have not implemented this method yet. You can also convert it to an Array using Array.from. In some cases, the NodeList is a live collection, which means that changes in the DOM are reflected in the collection.

译：尽管NodeList并非一个数组，但仍然可以使用forEach迭代。一些老旧的浏览器还没有实现这个方法，你可以使用Array.from将之转换成一个数组。某些情况下，NodeList时一个动态集合，这意味着DOM的变化会反应到collection中

基于上述原因，NodeList类型的实例不能被当成数组理解，它是动态集合。在insertNodeAfterNode执行完毕后，会引起DOM节点(htmlCollection[0])的更新，如此一来，htmlCollection[0]在每次执行完毕insertNodeAfterNode之后，都会发生变化，因此可以遍历全部的集合元素。