[聚合文章] 走进snabbdom—Vue2背后的Virtual-DOM的机制

snabbdom是一个Virtual-DOM的实现库，它专注于使用的简单以及功能和的模型化，并在效率和性能上有着很好的表现。如果你还不知道什么是Virtual-DOM技术，它是一种网页中通过diff算法来实现网页修改最小化的方法，react底层使用了这样的机制来提高性能。

从Vue2发布开始，也开始使用了这样的机制。Vue并没有选择自己重新造一套Virtual-DOM的算法，而是在snabbdom的基础上构建了一个嵌入了框架本身的fork版本。可以说，Vue就是在使用snabbdom的Virtual-DOM算法。

snabbdom 的特性

• snabbdom核心算法就两三百多行，阅读和理解都是非常方便的。
• module划分清楚，拓展性强
• 自带一系列hook，这些hook可以在diff算法的各处调用，可以使用hook定制过程
• 在Virtual-DOM众多算法中有着优秀的性能
• 函数都带有和自己签名相关的reduce/scan函数，方便函数响应式编程使用
• h函数可以简单的创建vnode节点
• 对于SVG，使用h函数可以轻松加上命名空间

snabbdom核心概念

• init

  snabbdom使用一种类似于插件声明使用的方式来模块化功能，如果你使用过AngularJS的声明注入或者Vue.use，你对这样的方式一定不陌生。

  var patch = snabbdom.init([
    require('snabbdom/modules/class').default,
    require('snabbdom/modules/style').default,
  ]);

• patch

  patch是由init返回的一个函数，第一个参数代表着之前的view，是一个vnode或者DOM节点，而第二个参数是一个新的vnode节点，oldNode会根据他的类型被相应的更新。

  patch(oldVnode, newVnode);

• h函数

  h函数可以让你更加轻松的建立vnode。

  var snabbdom = require('snabbdom')
  var patch = snabbdom.init([ // 调用init生成patch
    require('snabbdom/modules/class').default, // 让toggle class更加简单
    require('snabbdom/modules/props').default, // 让DOM可以设置props
    require('snabbdom/modules/style').default, // 支持带有style的元素，以及动画
    require('snabbdom/modules/eventlisteners').default, // 加上事件监听
  ]);
  var h = require('snabbdom/h').default; // h的意思是helper，帮助建立vnode
  var toVNode = require('snabbdom/tovnode').default;
  
  var newNode = h('div', {style: {color: '#000'}}, [
    h('h1', 'Headline'),
    h('p', 'A paragraph'),
  ]);
  
  patch(toVNode(document.querySelector('.container')), newVNode)

• 钩子（hook）

  名称	触发时间	回调参数
  pre	patch开始	none
  init	vnode被添加的时候	vnode
  create	DOM元素被从create创建	emptyVnode, vnode
  insert	一个元素被插入了DOM	vnode
  prepatch	元素即将被patch	oldVnode, vnode
  update	元素被更新	oldVnode, vnode
  postpatch	元素被patch后	oldVnode, vnode
  destroy	元素被直接或者间接移除	vnode
  remove	元素直接从DOM被移除	vnode, removeCallback
  post	patch操作结束	none

snabbdom 算法

diff两棵树的算法是一个O(n^3)的算法

对于两个元素，如果他们类型不同，或者key不同，那么元素就不是同一个元素，那么直接新的元素替换前一个元素。

对于两个元素是同一个元素的情况下，开始diff他们的附加元素，还有他们的children。

snabbdom在diff他们的children时候，一次性对比四个节点，oldNode与newNode的Children的首尾元素：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  // 开头处理了边界情况和特殊情况
      if (oldStartVnode == null) {
        // 如果oldStartVnode为空，那么往后移动继续探测
        oldStartVnode = oldCh[++oldStartIdx]; 
      } else if (oldEndVnode == null) {
        // 如果oldEndVnode为空，那么往前移动继续探测
        oldEndVnode = oldCh[--oldEndIdx];
      } else if (newStartVnode == null) {
        newStartVnode = newCh[++newStartIdx];
      } else if (newEndVnode == null) {
        newEndVnode = newCh[--newEndIdx];
        // 遇到空的节点的情况总是收缩边界搜索，直到边界条件跳出循环
      } else if (sameVnode(oldStartVnode, newStartVnode)) {
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
        oldStartVnode = oldCh[++oldStartIdx];
        newStartVnode = newCh[++newStartIdx];
        // 现在的首节点相同，diff他们两个的其他属性，并且start接着往后走
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
        oldEndVnode = oldCh[--oldEndIdx];
        newEndVnode = newCh[--newEndIdx];
        // 现在的尾节点相同，diff他们两个的其他属性，并且old接着往前走
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
        api.insertBefore(parentElm, oldStartVnode.elm as Node, 			 api.nextSibling(oldEndVnode.elm as Node));
        oldStartVnode = oldCh[++oldStartIdx];
        newEndVnode = newCh[--newEndIdx];
      } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
        api.insertBefore(parentElm, oldEndVnode.elm as Node, oldStartVnode.elm as Node);
        oldEndVnode = oldCh[--oldEndIdx];
        newStartVnode = newCh[++newStartIdx];
        // 首尾相同的情况，对旧的节点调整孩子顺序，并继续分别收缩范围
      } else {
        if (oldKeyToIdx === undefined) {
          oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
        }
        // 使用这里实现了Key和Index的对应索引
        idxInOld = oldKeyToIdx[newStartVnode.key as string];
        if (isUndef(idxInOld)) { // 这是一个新的元素
          api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm as Node);
          newStartVnode = newCh[++newStartIdx];
        } else {
          // 元素被移动，调换元素位置
          elmToMove = oldCh[idxInOld];
          if (elmToMove.sel !== newStartVnode.sel) {
            api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm as Node);
          } else {
            patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
            oldCh[idxInOld] = undefined as any;
            api.insertBefore(parentElm, (elmToMove.elm as Node), oldStartVnode.elm as Node);
          }
          newStartVnode = newCh[++newStartIdx];
        }
      }
    }
//元素不是被调换的情况下，那么创建或者删除元素
    if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
      if (oldStartIdx > oldEndIdx) {
        before = newCh[newEndIdx+1] == null ? null : newCh[newEndIdx+1].elm;
        addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);
      } else {
        removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
      }
    }

通过对于index与key的对应，以及特殊情况的对应，使diff算法的平均情况能够达到O(nlogn)。

而且根据init的注入，diff的内容还可以选择性的加入不同内容，来优化性能。