摘要：毫無疑問的是算法的復(fù)雜度與效率是決定能夠帶來性能提升效果的關(guān)鍵因素。速度略有損失，但可讀性大大提高。因此目前的主流算法趨向一致，在主要思路上，與的方式基本相同。在里面實現(xiàn)了的算法與支持。是唯一添加的方法所以只發(fā)生在中。

VirtualDOM是react在組件化開發(fā)場景下，針對DOM重排重繪性能瓶頸作出的重要優(yōu)化方案，而他最具價值的核心功能是如何識別并保存新舊節(jié)點數(shù)據(jù)結(jié)構(gòu)之間差異的方法，也即是diff算法。毫無疑問的是diff算法的復(fù)雜度與效率是決定VirtualDOM能夠帶來性能提升效果的關(guān)鍵因素。因此，在VirtualDOM方案被提出之后，社區(qū)中不斷涌現(xiàn)出對diff的改進算法，引用司徒正美的經(jīng)典介紹：

最開始經(jīng)典的深度優(yōu)先遍歷DFS算法，其復(fù)雜度為O(n^3)，存在高昂的diff成本，然后是cito.js的橫空出世，它對今后所有虛擬DOM的算法都有重大影響。它采用兩端同時進行比較的算法，將diff速度拉高到幾個層次。緊隨其后的是kivi.js，在cito.js的基出提出兩項優(yōu)化方案，使用key實現(xiàn)移動追蹤及基于key的編輯長度距離算法應(yīng)用（算法復(fù)雜度 為O(n^2)）。但這樣的diff算法太過復(fù)雜了，于是后來者snabbdom將kivi.js進行簡化，去掉編輯長度距離算法，調(diào)整兩端比較算法。速度略有損失，但可讀性大大提高。再之后，就是著名的vue2.0 把snabbdom整個庫整合掉了。

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

如果沒有理解virtual dom的構(gòu)建思想,那么你可以參考這篇精致文章Boiling React Down to a Few Lines in jQuery
virtual dom優(yōu)化開發(fā)的方式是：通過vnode,來實現(xiàn)無狀態(tài)組件,結(jié)合單向數(shù)據(jù)流(undirectional data flow),進行UI更新,整體代碼結(jié)構(gòu)是：

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具有一定的生態(tài)圈,如motorcycle.js,cycle-snabbdom,cerebral
4.snabbdom實現(xiàn)的十分優(yōu)雅,使用的是recursive方式調(diào)用patch,對比infernojs優(yōu)化痕跡明顯的代碼,snabbdom更易讀。
5.在閱讀過程中發(fā)現(xiàn),snabbdom的模塊化,插件支持做得極佳

我們來查看snabbdom基本使用方式。

// snabbdom在./snabbdom.js
var snabbdom = require("snabbdom")
// 初始化snabbdom,得到patch。隨后,我們可以看到snabbdom設(shè)計的精妙之處
var patch = snabbdom.init([
  require("snabbdom/modules/class"),
  require("snabbdom/modules/props"),
  require("snabbdom/modules/style"),
  require("snabbdom/modules/eventlisteners")
])
// h是一個生成vnode的包裝函數(shù),factory模式？對生成vnode更精細(xì)的包裝就是使用jsx
// 在工程里,我們通常使用webpack或者browserify對jsx編譯
var h = require("snabbdom/h")
// 構(gòu)造一個virtual dom,在實際中,我們通常希望一個無狀態(tài)的vnode
// 并且我們通過state來創(chuàng)造vnode
// react使用具有render方法的對象來作為組件,這個組件可以接受props和state
// 在snabbdom里面,我們同樣可以實現(xiàn)類似效果
// 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函數(shù)會對第一個參數(shù)做處理,如果第一個參數(shù)不是vnode,那么就把它包裝成vnode
// patch過后,vnode發(fā)生變化,代表了現(xiàn)在virtual dom的狀態(tài)
patch(container, vnode)
// 創(chuàng)建一個新的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上,現(xiàn)在newVnode代表vdom的狀態(tài)
patch(vnode, newVnode)

vnode的定義在./vnode.js中 vnode具備的屬性

1.tagName 可以是custom tag,可以是"div","span",etc,代表這個virtual dom的tag name
2.data, virtual dom數(shù)據(jù),它們與dom element的prop、attr的語義類似。但是virtual dom包含的數(shù)據(jù)可以更靈活。
比如利用./modules/class.js插件,我們在data里面輕松toggle一個類名

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

children,
對應(yīng)element的children,但是這是vdom的children。vdom的實現(xiàn)重點就在對children的patch上

text, 對應(yīng)element.textContent,在children里定義一個string,那么我們會為這個string創(chuàng)建一個textNode

elm, 對dom element的引用

key,用于提示children patch過程,隨后將詳細(xì)說明

隨后是h函數(shù)的包裝

h的實現(xiàn)在./h.js

包裝函數(shù)一共注意三點

對svg的包裝,創(chuàng)建svg需要namespace

將vdom.text統(tǒng)一轉(zhuǎn)化為string類型

將vdom.children中的string element轉(zhuǎn)化為textNode

與dom api的對接

實現(xiàn)在./htmldomapi.js

采用adapter模式,對dom api進行包裝,然后將htmldomapi作為默認(rèn)的瀏覽器接口
這種設(shè)計很機智。在擴展snabbdom的兼容性的時候,只需要改變snabbdom.init使用的瀏覽器接口,而不用改變patch等方法的實現(xiàn)

snabbdom的核心內(nèi)容實現(xiàn)在./snabbdom.js。snabbdom的核心實現(xiàn)不到三百行(233 sloc),非常簡短。

在snabbdom里面實現(xiàn)了snabbdom的virtual dom diff算法與virtual dom lifecycle hook支持。
virtual dom diff
vdom diff是virtual dom的核心算法,snabbdom的實現(xiàn)原理與react官方文檔Reconciliation一致
總結(jié)起來有：

對兩個樹結(jié)構(gòu)進行完整的diff和patch,復(fù)雜度增長為O(n^3),幾乎不可用

對兩個數(shù)結(jié)構(gòu)進行啟發(fā)式diff,將大大節(jié)省開銷

一篇閱讀量頗豐的文章React’s diff algorithm也說明的就是啟發(fā)過程,可惜,沒有實際的代碼參照。現(xiàn)在,我們根據(jù)snabbdom代碼來看啟發(fā)規(guī)則的運用,結(jié)束后,你會明白virtual dom的實現(xiàn)有多簡單。

首先來到snabbdom.js中init函數(shù)的return語句

return function(oldVnode, vnode) {
  var i, elm, parent;
  // insertedVnodeQueue存在于整個patch過程
  // 用于收集patch中新插入的vnode
  var insertedVnodeQueue = [];
  // 在進行patch之前,我們需要運行prepatch hook
  // cbs是init函數(shù)變量,即,這個return語句中函數(shù)的閉包
  // 這里,我們不理會lifecycle hook,而只關(guān)注vdom diff算法
  for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]();

  // 如果oldVnode不是vnode(在第一次調(diào)用時,oldVnode是dom element)
  // 那么用emptyNodeAt函數(shù)來將其包裝為vnode
  if (isUndef(oldVnode.sel)) {
    oldVnode = emptyNodeAt(oldVnode);
  }
  
  // sameVnode是上述“值不值得patch”的核心
  // sameVnode實現(xiàn)很簡單,查看兩個vnode的key與sel是否分別相同
  // ()=>{vnode1.key === vnode2.key && vnode1.sel === vnode2.
  // 比較語義不同的結(jié)構(gòu)沒有意義,比如diff一個"div"和"span"
  // 而應(yīng)該移除div,根據(jù)span vnode插入新的span
  // diff兩個key不相同的vnode同樣沒有意義
  // 指定key就是為了區(qū)分element
  // 對于不同key的element,不應(yīng)該去根據(jù)newVnode來改變oldVnode的數(shù)據(jù)
  // 而應(yīng)該移除不再oldVnode,添加newVnode
  if (sameVnode(oldVnode, vnode)) {
    // oldVnode與vnode的sel和key分別相同,那么這兩個vnode值得去比較
    //patchVnode根據(jù)vnode來更新oldVnode
    patchVnode(oldVnode, vnode, insertedVnodeQueue);
  } else {
    //不值得去patch的,我們就暴力點
    // 移除oldVnode,根據(jù)newVnode創(chuàng)建elm,并添加至parent中
    elm = oldVnode.elm;
    parent = api.parentNode(elm);

    // createElm根據(jù)vnode創(chuàng)建element
    createElm(vnode, insertedVnodeQueue);

    if (parent !== null) {
      // 將新創(chuàng)建的element添加到parent中
      api.insertBefore(parent, vnode.elm, api.nextSibling(elm));
      // 同時移除oldVnode
      removeVnodes(parent, [oldVnode], 0, 0);
    }
  }

  // 結(jié)束以后,調(diào)用插入vnode的insert hook
  for (i = 0; i < insertedVnodeQueue.length; ++i) {
    insertedVnodeQueue[i].data.hook.insert(insertedVnodeQueue[i]);
  }

  // 整個patch結(jié)束,調(diào)用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之前,調(diào)用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引用相同,則沒必要比較。在良好設(shè)計的vdom里,大部分時間我們都在執(zhí)行這個返回語句。
  if (oldVnode === vnode) return;
  // 如果兩次引用不同,那說明新的vnode創(chuàng)建了
  // 與之前一樣,我們先看這兩個vnode值不值得去patch
  if (!sameVnode(oldVnode, vnode)) {
    // 這四條語句是否與init返回函數(shù)里那四條相同？
    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的方法就是先調(diào)用全局的update hook
  // 然后調(diào)用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中規(guī)定,具有text屬性的vnode不應(yīng)該具備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,那么就調(diào)用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,我們改變對應(yīng)的elm.textContent
    // 在這里我們使用api.setText api
    api.setTextContent(elm, vnode.text);
  }
  if (isDef(hook) && isDef(i = hook.postpatch)) {
    i(oldVnode, vnode);
  }
}

patch的實現(xiàn)是否簡單明了？甚至有覺得“啊？這就patch完了”的感覺。當(dāng)然,我們還差最后一個,這個是重頭戲——updateChildren。

updateChildren的代碼較長且密集,但是算法十分簡單
oldCh是一個包含oldVnode的children數(shù)組,newCh同理
我們先遍歷兩個數(shù)組(while語句),維護四個變量

遍歷oldCh的頭索引 - oldStartIdx

遍歷oldCh的尾索引 - oldEndIdx

遍歷newCh的頭索引 - newStartIdx

遍歷newCh的尾索引 - newEndIdx

當(dāng)oldStartIdx > oldEndIdx或者newStartIdx > newOldStartIdx的時候停止遍歷。

遍歷過程中有五種比較
前四種比較

oldStartVnode和newStartVnode,兩者elm相對位置不變,若值得(sameVnode)比較,這patch這兩個vnode

oldEndVnode和newEndVnode,同上,elm相對位置不變,做相同patch檢測

oldStartVnode和newEndVnode,如果oldStartVnode和newEndVnode值得比較,說明oldCh中的這- - oldStartVnode.elm向右移動了。那么執(zhí)行api.insertBefore(parentElm,oldStartVnode.elm, api.nextSibling(oldEndVnode.elm))調(diào)整它的位置

oldEndVnode和newStartVnode,同上,但這是oldVnode.elm向左移,需要調(diào)整它的位置

最后一種比較

利用vnode.key,在ul>li*n的結(jié)構(gòu)里,我們很有可能使用key來標(biāo)志li的唯一性,那么我們就會來到最后一種情況。這個時候,我們先產(chǎn)生一個index-key表(createKeyToOldIdx),然后根據(jù)這個表來進行更改。

更改規(guī)則

如果newVnode.key不在表中,那么這個newVnode就是新的vnode,將其插入
如果newVnode.key在表中,那么對應(yīng)的oldVnode存在,我們需要patch這兩個vnode,并在patch之后,將這個oldVnode置為undefined(oldCh[idxInOld] = undefined),同時將oldVnode.elm位置變換到當(dāng)前oldStartIdx之前,以免影響接下來的遍歷

遍歷結(jié)束后,檢查四個變量,對移除剩余的oldCh或添加剩余的newCh
patch總結(jié)
閱讀完init函數(shù)return語句,patch,updateChildren,我們可以理解整個diff和patch的過程

有些函數(shù)createElm,removeVnodes并不重要

閱讀完virtual dom diff算法實現(xiàn)后,我們可能會奇怪,關(guān)于style、class、attr的patch在哪里？這些實現(xiàn)都在modules,并通過lifecycle發(fā)揮作用
snabbdom的生命周期鉤子函數(shù)定義在core doc - hook中。
再查看modules里的class會發(fā)現(xiàn),class module通過兩個hook鉤子來對elm的class進行patch。這兩個鉤子是create和update。
回到init函數(shù),這兩個鉤子在函數(shù)體開頭注冊

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中調(diào)用。createElm是唯一添加vnode的方法,所以insertedVnodeQueue.push只發(fā)生在createElm中。