React && VUE Virtual Dom的Diff算法统一之路 snabbd

摘要：毫无疑问的是算法的复杂度与效率是决定能够带来性能提升效果的关键因素。速度略有损失，但可读性大大提高。因此目前的主流算法趋向一致，在主要思路上，与的方式基本相同。在里面实现了的算法与支持。是唯一添加的方法所以只发生在中。

VirtualDOM是react在组件化开发场景下，针对DOM重排重绘性能瓶颈作出的重要优化方案，而他最具价值的核心功能是如何识别并保存新旧节点数据结构之间差异的方法，也即是diff算法。毫无疑问的是diff算法的复杂度与效率是决定VirtualDOM能够带来性能提升效果的关键因素。因此，在VirtualDOM方案被提出之后，社区中不断涌现出对diff的改进算法，引用司徒正美的经典介绍：

最开始经典的深度优先遍历DFS算法，其复杂度为O(n^3)，存在高昂的diff成本，然后是cito.js的横空出世，它对今后所有虚拟DOM的算法都有重大影响。它采用两端同时进行比较的算法，将diff速度拉高到几个层次。紧随其后的是kivi.js，在cito.js的基出提出两项优化方案，使用key实现移动追踪及基于key的编辑长度距离算法应用（算法复杂度 为O(n^2)）。但这样的diff算法太过复杂了，于是后来者snabbdom将kivi.js进行简化，去掉编辑长度距离算法，调整两端比较算法。速度略有损失，但可读性大大提高。再之后，就是著名的vue2.0 把snabbdom整个库整合掉了。

因此目前VirtualDOM的主流diff算法趋向一致，在主要diff思路上，snabbdom与react的reconilation方式基本相同。

如果没有理解virtual dom的构建思想,那么你可以参考这篇精致文章Boiling React Down to a Few Lines in jQuery
virtual dom优化开发的方式是：通过vnode,来实现无状态组件,结合单向数据流(undirectional data flow),进行UI更新,整体代码结构是：

var newVnode = render(vnode, state)
var oldVnode = patch(oldVnode, newVnode)
state.dispatch("change")
var newVnode = render(vnode, state)
var oldVnode = patch(oldVnode, newVnode)

在众多virtual dom库中,我们选择snabbdom库,原因有很多：

1.snabbdom性能排名靠前,虽然这个benchmark的参考性不高
2。snabbdom示例丰富
3.snabbdom具有一定的生态圈,如motorcycle.js,cycle-snabbdom,cerebral
4.snabbdom实现的十分优雅,使用的是recursive方式调用patch,对比infernojs优化痕迹明显的代码,snabbdom更易读。
5.在阅读过程中发现,snabbdom的模块化,插件支持做得极佳

我们来查看snabbdom基本使用方式。

// snabbdom在./snabbdom.js
var snabbdom = require("snabbdom")
// 初始化snabbdom,得到patch。随后,我们可以看到snabbdom设计的精妙之处
var patch = snabbdom.init([
  require("snabbdom/modules/class"),
  require("snabbdom/modules/props"),
  require("snabbdom/modules/style"),
  require("snabbdom/modules/eventlisteners")
])
// h是一个生成vnode的包装函数,factory模式？对生成vnode更精细的包装就是使用jsx
// 在工程里,我们通常使用webpack或者browserify对jsx编译
var h = require("snabbdom/h")
// 构造一个virtual dom,在实际中,我们通常希望一个无状态的vnode
// 并且我们通过state来创造vnode
// react使用具有render方法的对象来作为组件,这个组件可以接受props和state
// 在snabbdom里面,我们同样可以实现类似效果
// function component(state){return h(...)}
var vnode = 
  h(
    "div#container.two.classes", 
    {on: {click: someFn}}, 
    [ 
      h("span", {style: {fontWeight: "bold"}}, "This is bold"), 
      " and this is just normal text", 
      h("a", {props: {href: "/foo"}}, 
      "I"ll take you places!")
    ]
  )
// 得到初始的容器,注意container是一个dom element
var container = document.getElementById("container")
// 将vnode patch到container中
// patch函数会对第一个参数做处理,如果第一个参数不是vnode,那么就把它包装成vnode
// patch过后,vnode发生变化,代表了现在virtual dom的状态
patch(container, vnode)
// 创建一个新的vnode
var newVnode = 
  h(
    "div#container.two.classes", 
    {on: {click: anotherEventHandler}}, 
    [ 
      h("span", {style: {fontWeight: "normal", fontStyle: "italics"}},
      "This is now italics"), 
      " and this is still just normal text", 
      h("a", {props: {href: "/bar"}}, "I"ll take you places!")
    ]
  )
// 将新的vnode patch到vnode上,现在newVnode代表vdom的状态
patch(vnode, newVnode)

vnode的定义在./vnode.js中 vnode具备的属性

1.tagName 可以是custom tag,可以是"div","span",etc,代表这个virtual dom的tag name
2.data, virtual dom数据,它们与dom element的prop、attr的语义类似。但是virtual dom包含的数据可以更灵活。
比如利用./modules/class.js插件,我们在data里面轻松toggle一个类名

h("p", {class: {"hide": hideIntro}})

children,
对应element的children,但是这是vdom的children。vdom的实现重点就在对children的patch上

text, 对应element.textContent,在children里定义一个string,那么我们会为这个string创建一个textNode

elm, 对dom element的引用

key,用于提示children patch过程,随后将详细说明

随后是h函数的包装

h的实现在./h.js

包装函数一共注意三点

对svg的包装,创建svg需要namespace

将vdom.text统一转化为string类型

将vdom.children中的string element转化为textNode

与dom api的对接

实现在./htmldomapi.js

采用adapter模式,对dom api进行包装,然后将htmldomapi作为默认的浏览器接口
这种设计很机智。在扩展snabbdom的兼容性的时候,只需要改变snabbdom.init使用的浏览器接口,而不用改变patch等方法的实现

snabbdom的核心内容实现在./snabbdom.js。snabbdom的核心实现不到三百行(233 sloc),非常简短。

在snabbdom里面实现了snabbdom的virtual dom diff算法与virtual dom lifecycle hook支持。
virtual dom diff
vdom diff是virtual dom的核心算法,snabbdom的实现原理与react官方文档Reconciliation一致
总结起来有：

对两个树结构进行完整的diff和patch,复杂度增长为O(n^3),几乎不可用

对两个数结构进行启发式diff,将大大节省开销

一篇阅读量颇丰的文章React’s diff algorithm也说明的就是启发过程,可惜,没有实际的代码参照。现在,我们根据snabbdom代码来看启发规则的运用,结束后,你会明白virtual dom的实现有多简单。

首先来到snabbdom.js中init函数的return语句

return function(oldVnode, vnode) {
  var i, elm, parent;
  // insertedVnodeQueue存在于整个patch过程
  // 用于收集patch中新插入的vnode
  var insertedVnodeQueue = [];
  // 在进行patch之前,我们需要运行prepatch hook
  // cbs是init函数变量,即,这个return语句中函数的闭包
  // 这里,我们不理会lifecycle hook,而只关注vdom diff算法
  for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]();

  // 如果oldVnode不是vnode(在第一次调用时,oldVnode是dom element)
  // 那么用emptyNodeAt函数来将其包装为vnode
  if (isUndef(oldVnode.sel)) {
    oldVnode = emptyNodeAt(oldVnode);
  }
  
  // sameVnode是上述“值不值得patch”的核心
  // sameVnode实现很简单,查看两个vnode的key与sel是否分别相同
  // ()=>{vnode1.key === vnode2.key && vnode1.sel === vnode2.
  // 比较语义不同的结构没有意义,比如diff一个"div"和"span"
  // 而应该移除div,根据span vnode插入新的span
  // diff两个key不相同的vnode同样没有意义
  // 指定key就是为了区分element
  // 对于不同key的element,不应该去根据newVnode来改变oldVnode的数据
  // 而应该移除不再oldVnode,添加newVnode
  if (sameVnode(oldVnode, vnode)) {
    // oldVnode与vnode的sel和key分别相同,那么这两个vnode值得去比较
    //patchVnode根据vnode来更新oldVnode
    patchVnode(oldVnode, vnode, insertedVnodeQueue);
  } else {
    //不值得去patch的,我们就暴力点
    // 移除oldVnode,根据newVnode创建elm,并添加至parent中
    elm = oldVnode.elm;
    parent = api.parentNode(elm);

    // createElm根据vnode创建element
    createElm(vnode, insertedVnodeQueue);

    if (parent !== null) {
      // 将新创建的element添加到parent中
      api.insertBefore(parent, vnode.elm, api.nextSibling(elm));
      // 同时移除oldVnode
      removeVnodes(parent, [oldVnode], 0, 0);
    }
  }

  // 结束以后,调用插入vnode的insert hook
  for (i = 0; i < insertedVnodeQueue.length; ++i) {
    insertedVnodeQueue[i].data.hook.insert(insertedVnodeQueue[i]);
  }

  // 整个patch结束,调用cbs中的post hook
  for (i = 0; i < cbs.post.length; ++i) cbs.post[i]();
  return vnode;
};
```

    ###然后我们阅读patch的过程

```
function patchVnode(oldVnode, vnode, insertedVnodeQueue) {
  var i, hook;
  // 如前,在patch之前,调用prepatch hook,但是这个是vnode在data里定义的prepatch hook,而不是全局定义的prepatch hook
  if (isDef(i = vnode.data) && isDef(hook = i.hook) && isDef(i = hook.prepatch)) {
    i(oldVnode, vnode);
  }

  var elm = vnode.elm = oldVnode.elm, oldCh = oldVnode.children, ch = vnode.children;

  // 如果oldVnode和vnode引用相同,则没必要比较。在良好设计的vdom里,大部分时间我们都在执行这个返回语句。
  if (oldVnode === vnode) return;
  // 如果两次引用不同,那说明新的vnode创建了
  // 与之前一样,我们先看这两个vnode值不值得去patch
  if (!sameVnode(oldVnode, vnode)) {
    // 这四条语句是否与init返回函数里那四条相同？
    var parentElm = api.parentNode(oldVnode.elm);
    elm = createElm(vnode, insertedVnodeQueue);
    api.insertBefore(parentElm, elm, oldVnode.elm);
    removeVnodes(parentElm, [oldVnode], 0, 0);
    return;
  }
  // 这两个vnode值得去patch
  // 我们先patch vnode,patch的方法就是先调用全局的update hook
  // 然后调用vnode.data定义的update hook
  if (isDef(vnode.data)) {
    for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode);
    i = vnode.data.hook;
    if (isDef(i) && isDef(i = i.update)) i(oldVnode, vnode);
  }
  // patch两个vnode的text和children
  // 查看vnode.text定义
  // vdom中规定,具有text属性的vnode不应该具备children
  // 对于
foo:123
的良好写法是
  // h("p", [ "foo:", h("b", "123")]), 而非
  // h("p", "foo:", [h("b", "123")])
  if (isUndef(vnode.text)) {
    // vnode不是text node,我们再查看他们是否有children
    if (isDef(oldCh) && isDef(ch)) {
      // 两个vnode都有children,那么就调用updateChildren
      if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue);
    } else if (isDef(ch)) {
      // 只有新的vnode有children,那么添加vnode的children
      if (isDef(oldVnode.text)) api.setTextContent(elm, "");
      addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
    } else if (isDef(oldCh)) {
      // 只有旧vnode有children,那么移除oldCh
      removeVnodes(elm, oldCh, 0, oldCh.length - 1);
    } else if (isDef(oldVnode.text)) {
      // 两者都没有children,并且oldVnode.text不为空,vnode.text未定义,则清空elm.textContent
      api.setTextContent(elm, "");
    }
  } else if (oldVnode.text !== vnode.text) {
    // vnode是一个text node,我们改变对应的elm.textContent
    // 在这里我们使用api.setText api
    api.setTextContent(elm, vnode.text);
  }
  if (isDef(hook) && isDef(i = hook.postpatch)) {
    i(oldVnode, vnode);
  }
}

patch的实现是否简单明了？甚至有觉得“啊？这就patch完了”的感觉。当然,我们还差最后一个,这个是重头戏——updateChildren。

updateChildren的代码较长且密集,但是算法十分简单
oldCh是一个包含oldVnode的children数组,newCh同理
我们先遍历两个数组(while语句),维护四个变量

遍历oldCh的头索引 - oldStartIdx

遍历oldCh的尾索引 - oldEndIdx

遍历newCh的头索引 - newStartIdx

遍历newCh的尾索引 - newEndIdx

当oldStartIdx > oldEndIdx或者newStartIdx > newOldStartIdx的时候停止遍历。

遍历过程中有五种比较
前四种比较

oldStartVnode和newStartVnode,两者elm相对位置不变,若值得(sameVnode)比较,这patch这两个vnode

oldEndVnode和newEndVnode,同上,elm相对位置不变,做相同patch检测

oldStartVnode和newEndVnode,如果oldStartVnode和newEndVnode值得比较,说明oldCh中的这- - oldStartVnode.elm向右移动了。那么执行api.insertBefore(parentElm,oldStartVnode.elm, api.nextSibling(oldEndVnode.elm))调整它的位置

oldEndVnode和newStartVnode,同上,但这是oldVnode.elm向左移,需要调整它的位置

最后一种比较

利用vnode.key,在ul>li*n的结构里,我们很有可能使用key来标志li的唯一性,那么我们就会来到最后一种情况。这个时候,我们先产生一个index-key表(createKeyToOldIdx),然后根据这个表来进行更改。

更改规则

如果newVnode.key不在表中,那么这个newVnode就是新的vnode,将其插入
如果newVnode.key在表中,那么对应的oldVnode存在,我们需要patch这两个vnode,并在patch之后,将这个oldVnode置为undefined(oldCh[idxInOld] = undefined),同时将oldVnode.elm位置变换到当前oldStartIdx之前,以免影响接下来的遍历

遍历结束后,检查四个变量,对移除剩余的oldCh或添加剩余的newCh
patch总结
阅读完init函数return语句,patch,updateChildren,我们可以理解整个diff和patch的过程

有些函数createElm,removeVnodes并不重要

阅读完virtual dom diff算法实现后,我们可能会奇怪,关于style、class、attr的patch在哪里？这些实现都在modules,并通过lifecycle发挥作用
snabbdom的生命周期钩子函数定义在core doc - hook中。
再查看modules里的class会发现,class module通过两个hook钩子来对elm的class进行patch。这两个钩子是create和update。
回到init函数,这两个钩子在函数体开头注册

for (i = 0; i < hooks.length; ++i) {
  cbs[hooks[i]] = [];
  for (j = 0; j < modules.length; ++j) {
    if (modules[j][hooks[i]] !== undefined)
     cbs[hooks[i]].push(modules[j][hooks[i]]);
  }
}

create hook在createElm中调用。createElm是唯一添加vnode的方法,所以insertedVnodeQueue.push只发生在createElm中。