摘要：算法子節(jié)點(diǎn)比較這部分代碼比較多，先說說原理后面再貼代碼。循環(huán)結(jié)束的標(biāo)志就是舊子節(jié)點(diǎn)數(shù)組或新子節(jié)點(diǎn)數(shù)組遍歷完，即。第二步尾尾比較。第三步頭尾比較。第四步尾頭比較。節(jié)點(diǎn)確認(rèn)后，真實(shí)序列為，未確認(rèn)序列為第五次是均不相似，直接插入到未確認(rèn)序列頭部。

通過對 Vue2.0 源碼閱讀，想寫一寫自己的理解，能力有限故從尤大佬2016.4.11第一次提交開始讀，準(zhǔn)備陸續(xù)寫：

模版字符串轉(zhuǎn)AST語法樹
AST語法樹轉(zhuǎn)render函數(shù)
Vue雙向綁定原理
Vue虛擬dom比較原理

其中包含自己的理解和源碼的分析，盡量通俗易懂！由于是2.0的最早提交，所以和最新版本有很多差異、bug，后續(xù)將陸續(xù)補(bǔ)充，敬請諒解！包含中文注釋的Vue源碼已上傳...

先說一下為什么會(huì)有虛擬dom比較這一階段，我們知道了Vue是數(shù)據(jù)驅(qū)動(dòng)視圖（數(shù)據(jù)的變化將引起視圖的變化），但你發(fā)現(xiàn)某個(gè)數(shù)據(jù)改變時(shí)，視圖是局部刷新而不是整個(gè)重新渲染，如何精準(zhǔn)的找到數(shù)據(jù)對應(yīng)的視圖并進(jìn)行更新呢？那就需要拿到數(shù)據(jù)改變前后的dom結(jié)構(gòu)，找到差異點(diǎn)并進(jìn)行更新！

虛擬dom實(shí)質(zhì)上是針對真實(shí)dom提煉出的簡單對象。就像一個(gè)簡單的div包含200多個(gè)屬性，但真正需要的可能只有tagName，所以對真實(shí)dom直接操作將大大影響性能！

簡化后的虛擬節(jié)點(diǎn)（vnode）大致包含以下屬性：

{
  tag: "div",       // 標(biāo)簽名
  data: {},         // 屬性數(shù)據(jù)，包括class、style、event、props、attrs等
  children: [],     // 子節(jié)點(diǎn)數(shù)組，也是vnode結(jié)構(gòu)
  text: undefined,  // 文本
  elm: undefined,   // 真實(shí)dom
  key: undefined    // 節(jié)點(diǎn)標(biāo)識
}

虛擬dom的比較，就是找出新節(jié)點(diǎn)（vnode）和舊節(jié)點(diǎn)（oldVnode）之間的差異，然后對差異進(jìn)行打補(bǔ)丁（patch）。大致流程如下

整個(gè)過程還是比較簡單的，新舊節(jié)點(diǎn)如果不相似，直接根據(jù)新節(jié)點(diǎn)創(chuàng)建dom；如果相似，先是對data比較，包括class、style、event、props、attrs等，有不同就調(diào)用對應(yīng)的update函數(shù)，然后是對子節(jié)點(diǎn)的比較，子節(jié)點(diǎn)的比較用到了diff算法，這應(yīng)該是這篇文章的重點(diǎn)和難點(diǎn)吧。

值得注意的是，在Children Compare 過程中，如果找到了相似的childVnode，那它們將遞歸進(jìn)入新的打補(bǔ)丁過程。

這次的源碼解析寫簡潔一點(diǎn)，寫太多發(fā)現(xiàn)自己都不愿意看 (┬＿┬)

先來看patch()函數(shù)：

function patch (oldVnode, vnode) {
  var elm, parent;
  if (sameVnode(oldVnode, vnode)) {
    // 相似就去打補(bǔ)丁（增刪改）
    patchVnode(oldVnode, vnode);
  } else {
    // 不相似就整個(gè)覆蓋
    elm = oldVnode.elm;
    parent = api.parentNode(elm);
    createElm(vnode);
    if (parent !== null) {
      api.insertBefore(parent, vnode.elm, api.nextSibling(elm));
      removeVnodes(parent, [oldVnode], 0, 0);
    }
  }
  return vnode.elm;
}

patch()函數(shù)接收新舊vnode兩個(gè)參數(shù)，傳入的這兩個(gè)參數(shù)有個(gè)很大的區(qū)別：oldVnode的elm指向真實(shí)dom，而vnode的elm為undefined...但經(jīng)過patch()方法后，vnode的elm也將指向這個(gè)（更新過的）真實(shí)dom。

判斷新舊vnode是否相似的sameVnode()方法很簡單，就是比較tag和key是否一致。

function sameVnode (a, b) {
  return a.key === b.key && a.tag === b.tag;
}

對于新舊vnode不一致的處理方法很簡單，就是根據(jù)vnode創(chuàng)建真實(shí)dom，代替oldVnode中的elm插入DOM文檔。

對于新舊vnode一致的處理，就是我們前面經(jīng)常說到的打補(bǔ)丁了。具體什么是打補(bǔ)丁？看看patchVnode()方法就知道了：

function patchVnode (oldVnode, vnode) {
  // 新節(jié)點(diǎn)引用舊節(jié)點(diǎn)的dom
  let elm = vnode.elm = oldVnode.elm;
  const oldCh = oldVnode.children;
  const ch = vnode.children;

  // 調(diào)用update鉤子
  if (vnode.data) {
    updateAttrs(oldVnode, vnode);
    updateClass(oldVnode, vnode);
    updateEventListeners(oldVnode, vnode);
    updateProps(oldVnode, vnode);
    updateStyle(oldVnode, vnode);
  }

  // 判斷是否為文本節(jié)點(diǎn)
  if (vnode.text == undefined) {
    if (isDef(oldCh) && isDef(ch)) {
      if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue)
    } else if (isDef(ch)) {
      if (isDef(oldVnode.text)) api.setTextContent(elm, "")
      addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
    } else if (isDef(oldCh)) {
      removeVnodes(elm, oldCh, 0, oldCh.length - 1)
    } else if (isDef(oldVnode.text)) {
      api.setTextContent(elm, "")
    }
  } else if (oldVnode.text !== vnode.text) {
    api.setTextContent(elm, vnode.text)
  }
}

打補(bǔ)丁其實(shí)就是調(diào)用各種updateXXX()函數(shù)，更新真實(shí)dom的各個(gè)屬性。每個(gè)的update函數(shù)都類似，就拿updateAttrs()舉例看看：

function updateAttrs (oldVnode, vnode) {
  let key, cur, old
  const elm = vnode.elm
  const oldAttrs = oldVnode.data.attrs || {}
  const attrs = vnode.data.attrs || {}

  // 更新/添加屬性
  for (key in attrs) {
    cur = attrs[key]
    old = oldAttrs[key]
    if (old !== cur) {
      if (booleanAttrsDict[key] && cur == null) {
        elm.removeAttribute(key)
      } else {
        elm.setAttribute(key, cur)
      }
    }
  }
  // 刪除新節(jié)點(diǎn)不存在的屬性
  for (key in oldAttrs) {
    if (!(key in attrs)) {
      elm.removeAttribute(key)
    }
  }
}

屬性（Attribute）的更新函數(shù)的大致思路就是：

遍歷vnode屬性，如果和oldVnode不一樣就調(diào)用setAttribute()修改；

遍歷oldVnode屬性，如果不在vnode屬性中就調(diào)用removeAttribute()刪除。

你會(huì)發(fā)現(xiàn)里面有個(gè)booleanAttrsDict[key]的判斷，是用于判斷在不在布爾類型屬性字典中。

["allowfullscreen", "async", "autofocus", "autoplay", "checked", "compact", "controls", "declare", ......]
eg: ，想關(guān)閉自動(dòng)播放，需要移除該屬性。

所有數(shù)據(jù)比較完后，就到子節(jié)點(diǎn)的比較了。先判斷當(dāng)前vnode是否為文本節(jié)點(diǎn)，如果是文本節(jié)點(diǎn)就不用考慮子節(jié)點(diǎn)的比較；若是元素節(jié)點(diǎn)，就需要分三種情況考慮：

新舊節(jié)點(diǎn)都有children，那就進(jìn)入子節(jié)點(diǎn)的比較（diff算法）；

新節(jié)點(diǎn)有children，舊節(jié)點(diǎn)沒有，那就循環(huán)創(chuàng)建dom節(jié)點(diǎn)；

新節(jié)點(diǎn)沒有children，舊節(jié)點(diǎn)有，那就循環(huán)刪除dom節(jié)點(diǎn)。

后面兩種情況都比較簡單，我們直接對第一種情況，子節(jié)點(diǎn)的比較進(jìn)行分析。

子節(jié)點(diǎn)比較這部分代碼比較多，先說說原理后面再貼代碼。先看一張子節(jié)點(diǎn)比較的圖：

圖中的oldCh和newCh分別表示新舊子節(jié)點(diǎn)數(shù)組，它們都有自己的頭尾指針oldStartIdx，oldEndIdx，newStartIdx，newEndIdx，數(shù)組里面存儲(chǔ)的是vnode，為了容易理解就用a,b,c,d等代替，它們表示不同類型標(biāo)簽（div,span,p）的vnode對象。

子節(jié)點(diǎn)的比較實(shí)質(zhì)上就是循環(huán)進(jìn)行頭尾節(jié)點(diǎn)比較。循環(huán)結(jié)束的標(biāo)志就是：舊子節(jié)點(diǎn)數(shù)組或新子節(jié)點(diǎn)數(shù)組遍歷完，（即 oldStartIdx > oldEndIdx || newStartIdx > newEndIdx）。大概看一下循環(huán)流程：

第一步 頭頭比較。若相似，舊頭新頭指針后移（即 oldStartIdx++ && newStartIdx++），真實(shí)dom不變，進(jìn)入下一次循環(huán)；不相似，進(jìn)入第二步。

第二步 尾尾比較。若相似，舊尾新尾指針前移（即 oldEndIdx-- && newEndIdx--），真實(shí)dom不變，進(jìn)入下一次循環(huán)；不相似，進(jìn)入第三步。

第三步 頭尾比較。若相似，舊頭指針后移，新尾指針前移（即 oldStartIdx++ && newEndIdx--），未確認(rèn)dom序列中的頭移到尾，進(jìn)入下一次循環(huán)；不相似，進(jìn)入第四步。

第四步 尾頭比較。若相似，舊尾指針前移，新頭指針后移（即 oldEndIdx-- && newStartIdx++），未確認(rèn)dom序列中的尾移到頭，進(jìn)入下一次循環(huán)；不相似，進(jìn)入第五步。

第五步 若節(jié)點(diǎn)有key且在舊子節(jié)點(diǎn)數(shù)組中找到sameVnode（tag和key都一致），則將其dom移動(dòng)到當(dāng)前真實(shí)dom序列的頭部，新頭指針后移（即 newStartIdx++）；否則，vnode對應(yīng)的dom（vnode[newStartIdx].elm）插入當(dāng)前真實(shí)dom序列的頭部，新頭指針后移（即 newStartIdx++）。

先看看沒有key的情況，放個(gè)動(dòng)圖看得更清楚些！

相信看完圖片有更好的理解到diff算法的精髓，整個(gè)過程還是比較簡單的。上圖中一共進(jìn)入了6次循環(huán)，涉及了每一種情況，逐個(gè)敘述一下：

第一次是頭頭相似（都是a），dom不改變，新舊頭指針均后移。a節(jié)點(diǎn)確認(rèn)后，真實(shí)dom序列為：a,b,c,d,e,f，未確認(rèn)dom序列為：b,c,d,e,f；

第二次是尾尾相似（都是f），dom不改變，新舊尾指針均前移。f節(jié)點(diǎn)確認(rèn)后，真實(shí)dom序列為：a,b,c,d,e,f，未確認(rèn)dom序列為：b,c,d,e；

第三次是頭尾相似（都是b），當(dāng)前剩余真實(shí)dom序列中的頭移到尾，舊頭指針后移，新尾指針前移。b節(jié)點(diǎn)確認(rèn)后，真實(shí)dom序列為：a,c,d,e,b,f，未確認(rèn)dom序列為：c,d,e；

第四次是尾頭相似（都是e），當(dāng)前剩余真實(shí)dom序列中的尾移到頭，舊尾指針前移，新頭指針后移。e節(jié)點(diǎn)確認(rèn)后，真實(shí)dom序列為：a,e,c,d,b,f，未確認(rèn)dom序列為：c,d；

第五次是均不相似，直接插入到未確認(rèn)dom序列頭部。g節(jié)點(diǎn)插入后，真實(shí)dom序列為：a,e,g,c,d,b,f，未確認(rèn)dom序列為：c,d；

第六次是均不相似，直接插入到未確認(rèn)dom序列頭部。h節(jié)點(diǎn)插入后，真實(shí)dom序列為：a,e,g,h,c,d,b,f，未確認(rèn)dom序列為：c,d；

但結(jié)束循環(huán)后，有兩種情況需要考慮：

新的字節(jié)點(diǎn)數(shù)組（newCh）被遍歷完（newStartIdx > newEndIdx）。那就需要把多余的舊dom（oldStartIdx -> oldEndIdx）都刪除，上述例子中就是c,d；

新的字節(jié)點(diǎn)數(shù)組（oldCh）被遍歷完（oldStartIdx > oldEndIdx）。那就需要把多余的新dom（newStartIdx -> newEndIdx）都添加。

上面說了這么多都是沒有key的情況，說添加了:key可以優(yōu)化v-for的性能，到底是怎么回事呢？因?yàn)?b>v-for大部分情況下生成的都是相同tag的標(biāo)簽，如果沒有key標(biāo)識，那么相當(dāng)于每次頭頭比較都能成功。你想想如果你往v-for綁定的數(shù)組頭部push數(shù)據(jù)，那么整個(gè)dom將全部刷新一遍（如果數(shù)組每項(xiàng)內(nèi)容都不一樣），那加了key會(huì)有什么幫助呢？這邊引用一張圖：

有key的情況，其實(shí)就是多了一步匹配查找的過程。也就是上面循環(huán)流程中的第五步，會(huì)嘗試去舊子節(jié)點(diǎn)數(shù)組中找到與當(dāng)前新子節(jié)點(diǎn)相似的節(jié)點(diǎn)，減少dom的操作！

有興趣的可以看看代碼：

function updateChildren (parentElm, oldCh, newCh) {
  let oldStartIdx = 0
  let newStartIdx = 0
  let oldEndIdx = oldCh.length - 1
  let oldStartVnode = oldCh[0]
  let oldEndVnode = oldCh[oldEndIdx]
  let newEndIdx = newCh.length - 1
  let newStartVnode = newCh[0]
  let newEndVnode = newCh[newEndIdx]
  let oldKeyToIdx, idxInOld, elmToMove, before

  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (isUndef(oldStartVnode)) {
      oldStartVnode = oldCh[++oldStartIdx] // 未定義表示被移動(dòng)過
    } else if (isUndef(oldEndVnode)) {
      oldEndVnode = oldCh[--oldEndIdx]
    } else if (sameVnode(oldStartVnode, newStartVnode)) { // 頭頭相似
      patchVnode(oldStartVnode, newStartVnode)
      oldStartVnode = oldCh[++oldStartIdx]
      newStartVnode = newCh[++newStartIdx]
    } else if (sameVnode(oldEndVnode, newEndVnode)) { // 尾尾相似
      patchVnode(oldEndVnode, newEndVnode)
      oldEndVnode = oldCh[--oldEndIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldStartVnode, newEndVnode)) { // 頭尾相似
      patchVnode(oldStartVnode, newEndVnode)
      api.insertBefore(parentElm, oldStartVnode.elm, api.nextSibling(oldEndVnode.elm))
      oldStartVnode = oldCh[++oldStartIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldEndVnode, newStartVnode)) { // 尾頭相似
      patchVnode(oldEndVnode, newStartVnode)
      api.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
      oldEndVnode = oldCh[--oldEndIdx]
      newStartVnode = newCh[++newStartIdx]
    } else {
      // 根據(jù)舊子節(jié)點(diǎn)的key，生成map映射
      if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
      // 在舊子節(jié)點(diǎn)數(shù)組中，找到和newStartVnode相似節(jié)點(diǎn)的下標(biāo)
      idxInOld = oldKeyToIdx[newStartVnode.key]
      if (isUndef(idxInOld)) { 
        // 沒有key，創(chuàng)建并插入dom
        api.insertBefore(parentElm, createElm(newStartVnode), oldStartVnode.elm)
        newStartVnode = newCh[++newStartIdx]
      } else {
        // 有key，找到對應(yīng)dom ，移動(dòng)該dom并在oldCh中置為undefined
        elmToMove = oldCh[idxInOld]
        patchVnode(elmToMove, newStartVnode)
        oldCh[idxInOld] = undefined
        api.insertBefore(parentElm, elmToMove.elm, oldStartVnode.elm)
        newStartVnode = newCh[++newStartIdx]
      }
    }
  }
  // 循環(huán)結(jié)束時(shí)，刪除/添加多余dom
  if (oldStartIdx > oldEndIdx) {
    before = isUndef(newCh[newEndIdx+1]) ? null : newCh[newEndIdx + 1].elm
    addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
  } else if (newStartIdx > newEndIdx) {
    removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
  }
}

希望看完這篇對虛擬dom的比較會(huì)有一定的了解！如果有什么錯(cuò)誤記得悄悄告訴我啊哈哈。

文筆還是不好，希望大家能理解o(︶︿︶)o

4篇文章寫了兩個(gè)月......真是佩服自己的執(zhí)行力！但發(fā)現(xiàn)寫博客好像確實(shí)挺費(fèi)時(shí)的(┬＿┬)，不過以后一定會(huì)經(jīng)常寫，先兩周一篇？