摘要：原文地址此篇結(jié)合我最近造的小輪子進(jìn)行分析，其中的算法主要參考庫。如果其中一方?jīng)]有子節(jié)點(diǎn)，那么進(jìn)行刪除或添加。判斷是否一方已遍歷完，對(duì)真實(shí)進(jìn)行相應(yīng)的刪減或添加。

原文地址：https://github.com/HolyZheng/...
此篇結(jié)合我最近造的小輪子hoz進(jìn)行分析，其中的virtual dom算法主要參考snabbdom庫。

virtual dom的本質(zhì)是一個(gè)用來映射真實(shí)dom的JavaScript對(duì)象，比如

// hoz庫中的 src/vdom/vnode.js

class VNode {
  constructor (sel, tagName, id, className, el, children, data, text, key) {
    this.tagName = tagName // DIV
    this.sel = sel // div#id.class
    this.id = id // id
    this.className = className // []
    this.children = children // []
    this.el = el // node
    this.data = data // {}
    this.key = key
    this.text = text
  }
}

通過一個(gè)vnode對(duì)象去對(duì)應(yīng)一個(gè)dom元素，vnode的屬性對(duì)應(yīng)反映dom元素的屬性。然后我們可以定義一個(gè)toVnode方法，把一個(gè)dom tree轉(zhuǎn)為virtual dom tree。

// hoz庫中 src/vdom/toVnode.js

import VNode from "./vnode"
import * as utils from "./is"

function toVnode (node, utilsTool) {
  const api = (utilsTool === undefined ? utils : utilsTool) // 自定義的一些工具
  let text

// 判斷是否為node節(jié)點(diǎn)，不是拋出錯(cuò)誤
  if (!node) {
    throw new Error("Please make sure you have pass the argument "node" in to function toVnode")
  }

// 如果是element類型節(jié)點(diǎn)
  if (api.isElement(node)) {

   // 收集該節(jié)點(diǎn)各屬性信息，這里實(shí)現(xiàn)方式比較多，只要獲取到需要的足夠的信息就行了
  // 這里獲取了id，類名cn，類名數(shù)組ca，類字符串如 .classA.classB，sel 等等
    const id = node.id ? node.id : ""
    const cn = node.getAttribute("class")
    const ca = cn ? cn.split(" ") : null // classArray
    const c = cn ? "." + cn.split(" ").join(".") : "" // .classA.classB
    const sel = node.tagName.toLowerCase() + "#" + id + c
    const attrs = {}
    const elmAttrs = node.attributes
    const elmChildren = node.childNodes
    const children = elmChildren.length ? [] : null
    const tag = node.tagName
    let i, n
  
    for (i = 0, n = elmAttrs.length; i < n; i++) {
      if (elmAttrs[i].nodeName !== "class" && elmAttrs[i].nodeName !== "id") {
        // id 和 class例外處理
        attrs[elmAttrs[i].nodeName] = elmAttrs[i].nodeValue
      }
    }

// 如果給節(jié)點(diǎn)指定了key屬性，則獲取key的值
    const key = attrs.key ? attrs.key : undefined

// 如果有子節(jié)點(diǎn)，對(duì)子節(jié)點(diǎn)遞歸調(diào)用toVnode方法
    for (i = 0, n = elmChildren.length; i < n; i++) {
      children.push(toVnode(elmChildren[i], api))
    }
    return new VNode(sel, tag, id, ca, node, children, attrs, undefined, key)

// 文本節(jié)點(diǎn)
  } else if (api.isText(node)) {
    text = node.textContent
    return new VNode(undefined, undefined, undefined, undefined, node, undefined, undefined, text, undefined)

// 注釋節(jié)點(diǎn)
  } else if (api.isComment(node)) {
    text = node.textContent
    return new VNode("commont", undefined, undefined, undefined, node, undefined, undefined, text, undefined)
  } else {
    return new VNode("", undefined, undefined, undefined, node, undefined, undefined, undefined, undefined)
  }
}

export default toVnode

toVnode方法說白了就是，判斷當(dāng)前節(jié)點(diǎn)類型，創(chuàng)建對(duì)應(yīng)類型的vnode，然后如果有子節(jié)點(diǎn)的話，對(duì)子節(jié)點(diǎn)遞歸調(diào)用toVnode方法，將子節(jié)點(diǎn)也轉(zhuǎn)為vnode，執(zhí)行結(jié)束后，我們就可以得到一棵以傳入節(jié)點(diǎn)為根節(jié)點(diǎn)的virtual dom tree了。

到這里我們已經(jīng)有了一個(gè)映射真實(shí)dom的virtual dom類（vnode），以及一個(gè)將dom轉(zhuǎn)為virtual dom方法（toVnode）

接下來到了關(guān)鍵的diff算法，diff算法就是用來對(duì)比新舊兩個(gè)vnode，計(jì)算出最小的修改單位，去操作更新真實(shí)的dom。下面是一張解釋diff流程的經(jīng)典圖，我相信你不是第一次看到

diff會(huì)算法會(huì)在同一層比較新舊兩個(gè)vnode，從而將算法復(fù)雜度降低到O(n)。hoz庫中diff算法的實(shí)現(xiàn)在patch.js文件中，這里面有幾個(gè)關(guān)鍵的函數(shù)

/**
 * 比較新老節(jié)點(diǎn)，相同則進(jìn)行patchVnode，不同的話在真實(shí)dom上
 * 用新的節(jié)點(diǎn)，取代舊的節(jié)點(diǎn)。
 */

export default function patch (oldVnode, vnode) {
  if (sameVnode(oldVnode, vnode)) {
    patchVnode(oldVnode, vnode)
  } else {
    const oldElement = oldVnode.el
    let parentElement = api.parentNode(oldElement)
    createElm(vnode)
    if (parentElement !== null) {
      api.insertBefore(parentElement, vnode.el, api.nextSibling(oldElement))
      api.removeChild(parentElement, oldVnode.el)
    }
  }
  return vnode
}

第一個(gè)關(guān)鍵函數(shù)就是我們diff算法的入口函數(shù)patch方法，該方法負(fù)責(zé)，判斷oldVnode,和vnode是否為同一節(jié)點(diǎn)，如果是，調(diào)用patchVnode方法，進(jìn)一步比較處理，不是的話，用新節(jié)點(diǎn)代替就節(jié)點(diǎn)。

ps：通過sameVnode進(jìn)行判斷

function sameVnode (oldVnode, vnode) {
  return vnode.key === oldVnode.key && vnode.tagName === oldVnode.tagName
  // 這里可按自己需要進(jìn)行比較
}

上面提到，如果是同一節(jié)點(diǎn)的話，就會(huì)進(jìn)入到patchVnode方法中

function patchVnode (oldVnode, vnode) {
  const element = vnode.el = oldVnode.el
  let oldCh = oldVnode.children
  let ch = vnode.children
  // 如果相同，不需要比較
  if (oldVnode === vnode) {
    console.log("oldVnode === vnode")
    return
  }
  if (oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text) {
    api.setTextContent(element, vnode.text)
  } else {
    // 更新element的className, id, 和其他屬性
    updateElm(element, vnode)
    if (oldCh && ch && oldCh !== ch) {
      updateChildren(element, oldCh, ch)
    } else if (ch) {
      // 新vnode有子節(jié)點(diǎn)，oldvnode沒有子節(jié)點(diǎn)，給element添加子節(jié)點(diǎn)
      addVnodes(element, null, ch, 0, ch.length - 1)
    } else if (oldCh) {
      // 新vnode沒有子節(jié)點(diǎn)，oldvnode有子節(jié)點(diǎn)，給element刪除子節(jié)點(diǎn)
      removeVnodes(element, oldCh, 0, oldCh.length - 1)
    }
  }
}

patchVnode方法的任務(wù)就是

比較oldVnode與vnode，如果兩者完全相同，沒有變化的話，直接return。不同的話，用新的vnode去更新oldVnode。

比較它們的子節(jié)點(diǎn)，如果都由子節(jié)點(diǎn)，調(diào)用updateChildren去比較它們的子節(jié)點(diǎn)。

如果其中一方?jīng)]有子節(jié)點(diǎn)，那么進(jìn)行dom刪除或添加。

添加節(jié)點(diǎn)：通過addVnode，遍歷vnode子節(jié)點(diǎn)，調(diào)用createElm創(chuàng)建真實(shí)dom，插入到真實(shí)dom中。

刪除節(jié)點(diǎn)：通過removeVnode，遍歷oldvnode，并從真實(shí)dom中刪除。

剛剛說到，如果它們都有子節(jié)點(diǎn)，那么會(huì)調(diào)用updateChildren去繼續(xù)比較它們的子節(jié)點(diǎn)，updateChildren是這里的難點(diǎn)，可以說，最復(fù)雜的操作就是這一步，代碼

function updateChildren (parentElm, oldCh, newCh) {
  let oldStartIdx = 0
  let newStartIdx = 0
  let oldEndIdx = oldCh.length - 1
  let newEndIdx = newCh.length - 1
  let oldStartVnode = oldCh[0]
  let newStartVnode = newCh[0]
  let oldEndVnode = oldCh[oldEndIdx]
  let newEndVnode = newCh[newEndIdx]
  let oldKeyToIdx
  let idxInOld
  let emlToMove
  let before
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // oldStartIdx 與 oldEndIdx 與 newStartIdx 與 newEndIdx 之間四中比較
    // 簡單的判斷子節(jié)點(diǎn)的移位
    if (oldStartVnode == null) {
      oldStartVnode = oldCh[++oldStartIdx]
    } else if (oldEndVnode == null) {
      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)
      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.el, api.nextSibling(oldEndVnode.el))
      oldStartVnode = oldCh[++oldStartIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldEndVnode, newStartVnode)) {
      patchVnode(oldEndVnode, newStartVnode)
      api.insertBefore(parentElm, oldEndVnode.el, oldStartVnode.el)
      oldEndVnode = oldCh[--oldEndIdx]
      newStartVnode = newCh[++newStartIdx]
    } else {
      if (oldKeyToIdx === undefined) {
        oldKeyToIdx = createKeyToOldIndex(oldCh, oldStartIdx, oldEndIdx)
      }
      idxInOld = oldKeyToIdx[newStartVnode.key]
      // idx 不存在，說明該節(jié)點(diǎn)是新增的，原來沒有的，故創(chuàng)建一個(gè)新節(jié)點(diǎn)，并插入
      if (!idxInOld) {
        api.insertBefore(parentElm, createElm(newStartVnode), oldStartVnode.el)
        newStartVnode = newCh[++newStartIdx]
      } else {
        emlToMove = oldCh[idxInOld]
        // sel 不同的話，證明也是一個(gè)原來沒有的節(jié)點(diǎn)，所以創(chuàng)建并插入
        if (emlToMove.sel !== newStartVnode.sel) {
          api.insertBefore(parentElm, createElm(newStartVnode), oldStartVnode.el)
        } else {
          patchVnode(emlToMove, newStartVnode)
          oldCh[idxInOld] = null
          api.insertBefore(parentElm, emlToMove.el, oldStartVnode.el)
        }
        newStartVnode = newCh[++newStartIdx]
      }
    }
  }
  // 這是oldVnode已經(jīng)遍歷完，vnode還沒有，說明vnode比oldVnode節(jié)點(diǎn)多，所以將多出的節(jié)點(diǎn)創(chuàng)建并插入
  if (oldStartIdx > oldEndIdx) {
    before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].el
    addVnodes(parentElm, before, newCh, newStartIdx, oldEndIdx)
  } else {
    removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
  }
}

下面圖反映了updateChildren的運(yùn)作方式

將oldStartIdx，oldEndIdx，newStartIdx，newEndIdx分別指向同層新舊vnode的首尾，然后隨著比較而逐漸往中間移動(dòng)，對(duì)4個(gè)節(jié)點(diǎn)進(jìn)行比較，會(huì)有4種比較結(jié)果，（oldStartIdx和newStartIdx或newEndIdx指向同一節(jié)點(diǎn)，oldEndIdx和newStartIdx或newEndIdx指向同一節(jié)點(diǎn)這四種），根據(jù)4個(gè)節(jié)點(diǎn)的的4種比較結(jié)果做相應(yīng)的操作，比如當(dāng)出現(xiàn)oldStartIdx和newStartIdx指向同一節(jié)點(diǎn)這個(gè)結(jié)果時(shí)，表示這個(gè)節(jié)點(diǎn)不需要進(jìn)行移位操作，直接調(diào)用patchVnode進(jìn)行進(jìn)一步比較，又比如出現(xiàn)oldStartIdx和newEndIdx指向同一節(jié)點(diǎn)這一結(jié)果，那么表示oldStartIdx指向的節(jié)點(diǎn)需要移動(dòng)到oldEndIdx后面去，然后再對(duì)他們調(diào)用patchVnode進(jìn)行進(jìn)一步比較。

如果4種結(jié)果都不是，調(diào)用createKeyToOldIndex 方法，創(chuàng)建一個(gè)key與oldIndex之間的映射的map，查看newStartVnode.key是否有對(duì)應(yīng)的oldVnode，如果有，說明oldvnode移動(dòng)到了oldStartVnode前面，然后將對(duì)應(yīng)的oldVnode插入到oldStartVnode前面，如果沒有，說明在當(dāng)前newStartVnode是新創(chuàng)建得節(jié)點(diǎn)，在oldStartVnode前面插入該節(jié)點(diǎn)。

判斷是否一方已遍歷完，對(duì)真實(shí)dom進(jìn)行相應(yīng)的刪減或添加。

這就是diff得大致流程了。