摘要：很多人認為虛擬最大的優勢是算法，減少操作真實的帶來的性能消耗。雖然這一個虛擬帶來的一個優勢，但并不是全部?；氐阶铋_始的問題，虛擬到底是什么，說簡單點，就是一個普通的對象，包含了三個屬性。

虛擬 DOM （Virtual DOM ）這個概念相信大家都不陌生，從 React 到 Vue ，虛擬 DOM 為這兩個框架都帶來了跨平臺的能力（React-Native 和 Weex）。因為很多人是在學習 React 的過程中接觸到的虛擬 DOM ，所以為先入為主，認為虛擬 DOM 和 JSX 密不可分。其實不然，虛擬 DOM 和 JSX 固然契合，但 JSX 只是虛擬 DOM 的充分不必要條件，Vue 即使使用模版，也能把虛擬 DOM 玩得風生水起，同時也有很多人通過 babel 在 Vue 中使用 JSX。

很多人認為虛擬 DOM 最大的優勢是 diff 算法，減少 JavaScript 操作真實 DOM 的帶來的性能消耗。雖然這一個虛擬 DOM 帶來的一個優勢，但并不是全部。虛擬 DOM 最大的優勢在于抽象了原本的渲染過程，實現了跨平臺的能力，而不僅僅局限于瀏覽器的 DOM，可以是安卓和 IOS 的原生組件，可以是近期很火熱的小程序，也可以是各種GUI。

回到最開始的問題，虛擬 DOM 到底是什么，說簡單點，就是一個普通的 JavaScript 對象，包含了 tag、props、children 三個屬性。

  
hello world!!!

上面的 HTML 轉換為虛擬 DOM 如下：

{
  tag: "div",
  props: {
    id: "app"
  },
  chidren: [
    {
      tag: "p",
      props: {
        className: "text"
      },
      chidren: [
        "hello world!!!"
      ]
    }
  ]
}

該對象就是我們常說的虛擬 DOM 了，因為 DOM 是樹形結構，所以使用 JavaScript 對象就能很簡單的表示。而原生 DOM 因為瀏覽器廠商需要實現眾多的規范（各種 HTML5 屬性、DOM事件），即使創建一個空的 div 也要付出昂貴的代價。虛擬 DOM 提升性能的點在于 DOM 發生變化的時候，通過 diff 算法比對 JavaScript 原生對象，計算出需要變更的 DOM，然后只對變化的 DOM 進行操作，而不是更新整個視圖。

那么我們到底該如何將一段 HTML 轉換為虛擬 DOM 呢？

觀察主流的虛擬 DOM 庫（snabbdom、virtual-dom），通常都有一個 h 函數，也就是 React 中的 React.createElement，以及 Vue 中的 render 方法中的 createElement，另外 React 是通過 babel 將 jsx 轉換為 h 函數渲染的形式，而 Vue 是使用 vue-loader 將模版轉為 h 函數渲染的形式（也可以通過 babel-plugin-transform-vue-jsx 插件在 vue 中使用 jsx，本質還是轉換為 h 函數渲染形式）。

我們先使用 babel，將一段 jsx 代碼，轉換為一段 js 代碼：

npm i -D @babel/cli @babel/core @babel/plugin-transform-react-jsx

{
    "plugins": [
        [
            "@babel/plugin-transform-react-jsx",
            {
                "pragma": "h", // default pragma is React.createElement
            }
        ]
    ]
}

在目錄下新建一個 main.jsx

function getVDOM() {
  return (
    

      
hello world!!!
    
  )
}

使用如下命令進行轉譯：

npx babel main.jsx --out-file main-compiled.js

可以看到，最終 HTML 代碼會被轉譯成 h 函數的渲染形式。h 函數接受是三個參數，分別代表是 DOM 元素的標簽名、屬性、子節點，最終返回一個虛擬 DOM 的對象。

function h(tag, props, ...children) {
  return {
    tag,
    props: props || {},
    children: children.flat()
  }
}

雖然虛擬 DOM 可以渲染到多個平臺，但是這里講一下在瀏覽器環境下如何渲染虛擬 DOM。

function render(vdom) {
  // 如果是字符串或者數字，創建一個文本節點
  if (typeof vdom === "string" || typeof vdom === "number") {
    return document.createTextNode(vdom)
  }
  const { tag, props, children } = vdom
  // 創建真實DOM
  const element = document.createElement(tag)
  // 設置屬性
  setProps(element, props)
  // 遍歷子節點，并獲取創建真實DOM，插入到當前節點
  children
    .map(render)
    .forEach(element.appendChild.bind(element))

  // 虛擬 DOM 中緩存真實 DOM 節點
  vdom.dom = element
  
  // 返回 DOM 節點
  return element
}

function setProps (element, props) {
  Object.entries(props).forEach(([key, value]) => {
    setProp(element, key, value)
  })
}

function setProp (element, key, vlaue) {
  element.setAttribute(
    // className使用class代替
    key === "className" ? "class" : key,
    vlaue
  )
}

將虛擬 DOM 渲染成真實 DOM 后，只需要插入到對應的根節點即可。

const vdom = 
hello world!!!
 // h("div", {}, "hello world!!!")
const app = document.getElementById("app")
const ele = render(vdom)
app.appendChild(ele)

當然在現代化的框架中，一般會有一個組件文件專門用來構造虛擬 DOM，我們模仿 React 使用 class 的方式編寫組件，然后渲染到頁面中。

class Component {
  vdom = null // 組件的虛擬DOM表示
  $el  = null // 虛擬DOM生成的真實節點

  state = {
    text: "Initialize the Component"
  }
  
  render() {
    const { text } = this.state
    return (
      
{ text }
    )
  }
}

function createElement (app, component) {
  const vdom = component.render()
  component.vdom = vdom
  component.$el = render(vdom) // 將虛擬 DOM 轉換為真實 DOM
  app.appendChild(component.$el)
}

const app = document.getElementById("app")
const component = new Component
createElement(app, component)

diff 算法，顧名思義，就是比對新老 VDOM 的變化，然后將變化的部分更新到視圖上。對應到代碼上，就是一個 diff 函數，返回一個 patches （補?。?。

const before  = h("div", {}, "before text")
const after   = h("div", {}, "after text")

const patches = diff(before, after)

修改我們之前的組件，增加 setState 方法，用于修改組件的內部狀態。

class Component {
  vdom = null // 組件的虛擬DOM表示
  $el = null // 虛擬DOM生成的真實節點
  
  state = {
    text: "Initialize the Component"
  }
  
  // 手動修改組件state
  setState(newState) {
    this.state = {
      ...this.state,
      ...newState
    }
    const newVdom = this.render()
    const patches = diff(this.vdom, newVdom)
    patch(this.$el, patches)
  }

  changeText(text) {
    this.setState({
      text
    })
  }
  
  render() {
    const { text } = this.state
    return (
      
{ text }
    )
  }
}

當我們調用 setState 時，state 內部狀態發生變動，再次調用 render 方法就會生成一個新的虛擬 DOM 樹，這樣我們就能使用 diff 方法計算出新老虛擬 DOM 發送變化的部分，最后使用 patch 方法，將變動渲染到視圖中。

const app = document.getElementById("app")
const component = new Component
createElement(app, component)

// 將文本更改為數字，每秒 +1
let count = 0
setInterval(() => {
  component.changeText(++count)
}, 1000);

關于 diff 算法的最經典的就是 Matt Esch 的 virtual-dom，以及 snabbdom（被整合進 vue 2.0中）。

最開始出現的是 virtual-dom 這個庫，是大家好奇 React 為什么這么快而搞鼓出來的。它的實現是非常學院風格，通過深度優先搜索與 in-order tree 來實現高效的 diff 。它與 React 后來公開出來的算法是很不一樣。
然后是 cito.js 的橫空出世，它對今后所有虛擬 DOM 的算法都有重大影響。它采用兩端同時進行比較的算法，將 diff 速度拉高到幾個層次。
緊隨其后的是 kivi.js，在 cito.js 的基出提出兩項優化方案，使用 key 實現移動追蹤以及及基于 key 的最長自增子序列算法應用（算法復雜度 為O(n^2)）。
但這樣的 diff 算法太過復雜了，于是后來者 snabbdom 將 kivi.js 進行簡化，去掉編輯長度矩離算法，調整兩端比較算法。速度略有損失，但可讀性大大提高。再之后，就是著名的vue2.0 把sanbbdom整個庫整合掉了。
引用自司徒正美的文章 去哪兒網迷你React的研發心得

下面我們就來講講這幾個虛擬 DOM 庫 diff 算法的具體實現：

virtual-dom 作為虛擬 DOM 開天辟地的作品，采用了對 DOM 樹進行了深度優先的遍歷的方法。

體現到代碼上：

function diff (oldNode, newNode) {
  const patches = []
  walk(oldNode, newNode, patches, 0) // 進行深度優先遍歷
  return patches
}

function walk(oldNode, newNode, patches, index) {
  if (newNode === oldNode) {
    return
  }
  
  const patch = { type: "update", vNode: newNode }
  
  const oldChildren = oldNode.children
  const newChildren = newNode.children
  const oldLen = oldChildren.length
  const newLen = newChildren.length
  const len = oldLen > newLen ? oldLen : newLen
  // 找到對應位置的子節點進行比對
  for (let i = 0; i < len; i++) {
    const oldChild = oldChildren[i]
    const newChild = newChildren[i]
    index++
    // 相同節點進行比對
    walk(oldChild, newChild, patches, index)
    if (isArray(oldChild.children)) {
      index += oldChild.children.length
    }
  }
  
  if (patch) {
    patches[index] = patch
  }
}

上面代碼只是對 VDOM 進行了簡單的深度優先遍歷，在遍歷中，還需要對每個 VDOM 進行一些對比，具體分為以下幾種情況：

舊節點不存在，插入新節點；新節點不存在，刪除舊節點

新舊節點如果都是 VNode，且新舊節點 tag 相同

對比新舊節點的屬性

對比新舊節點的子節點差異，通過 key 值進行重排序，key 值相同節點繼續向下遍歷

新舊節點如果都是 VText，判斷兩者文本是否發生變化

其他情況直接用新節點替代舊節點

import { isVNode, isVText, isArray } from "../utils/type"

function walk(oldNode, newNode, patches, index) {
  if (newNode === oldNode) {
    return
  }

  let patch = patches[index]

  if (!oldNode) {
    // 舊節點不存在，直接插入
    patch = appendPatch(patch, {
      type: PATCH.INSERT,
      vNode: newNode,
    })
  } else if (!newNode) {
    // 新節點不存在，刪除舊節點
    patch = appendPatch(patch, {
      type: PATCH.REMOVE,
      vNode: null,
    })
  } else if (isVNode(newNode)) {
    if (isVNode(oldNode)) {
      // 相同類型節點的 diff
      if (newNode.tag === oldNode.tag && newNode.key === oldNode.key) {
        // 新老節點屬性的對比
        const propsPatch = diffProps(newNode.props, oldNode.props)
        if (propsPatch && propsPatch.length > 0) {
          patch = appendPatch(patch, {
            type: PATCH.PROPS,
            patches: propsPatch,
          })
        }
        // 新老節點子節點的對比
        patch = diffChildren(oldNode, newNode, patches, patch, index)
      }
    } else {
      // 新節點替換舊節點
      patch = appendPatch(patch, {
        type: PATCH.REPLACE,
        vNode: newNode,
      })
    }
  } else if (isVText(newNode)) {
    if (!isVText(oldNode)) {
      // 將舊節點替換成文本節點
      patch = appendPatch(patch, {
        type: PATCH.VTEXT,
        vNode: newNode,
      })
    } else if (newNode.text !== oldNode.text) {
      // 替換文本
      patch = appendPatch(patch, {
        type: PATCH.VTEXT,
        vNode: newNode,
      })
    }
  }

  if (patch) {
    // 將補丁放入對應位置
    patches[index] = patch
  }
}

// 一個節點可能有多個 patch
// 多個patch時，使用數組進行存儲
function appendPatch(patch, apply) {
  if (patch) {
    if (isArray(patch)) {
      patch.push(apply)
    } else {
      patch = [patch, apply]
    }

    return patch
  } else {
    return apply
  }
}

function diffProps(newProps, oldProps) {
  const patches = []
  const props = Object.assign({}, newProps, oldProps)

  Object.keys(props).forEach(key => {
    const newVal = newProps[key]
    const oldVal = oldProps[key]
    if (!newVal) {
      patches.push({
        type: PATCH.REMOVE_PROP,
        key,
        value: oldVal,
      })
    }

    if (oldVal === undefined || newVal !== oldVal) {
      patches.push({
        type: PATCH.SET_PROP,
        key,
        value: newVal,
      })
    }
  })

  return patches
}

這一部分可以說是 diff 算法中，變動最多的部分，因為前面的部分，各個庫對比的方向基本一致，而關于子節點的對比，各個倉庫都在前者基礎上不斷得進行改進。

首先需要明白，為什么需要改進子節點的對比方式。如果我們直接按照深度優先遍歷的方式，一個個去對比子節點，子節點的順序發生改變，那么就會導致 diff 算法認為所有子節點都需要進行 replace，重新將所有子節點的虛擬 DOM 轉換成真實 DOM，這種操作是十分消耗性能的。

但是，如果我們能夠找到新舊虛擬 DOM 對應的位置，然后進行移動，那么就能夠盡量減少 DOM 的操作。

virtual-dom 在一開始就進行了這方面的嘗試，對子節點添加 key 值，通過 key 值的對比，來判斷子節點是否進行了移動。通過 key 值對比子節點是否移動的模式，被各個庫沿用，這也就是為什么主流的視圖庫中，子節點如果缺失 key 值，會有 warning 的原因。

具體是怎么對比的，我們先看代碼：

function diffChildren(oldNode, newNode, patches, patch, index) {
  const oldChildren = oldNode.children
  // 新節點按舊節點的順序重新排序
  const sortedSet = sortChildren(oldChildren, newNode.children)
  const newChildren = sortedSet.children
  const oldLen = oldChildren.length
  const newLen = newChildren.length
  const len = oldLen > newLen ? oldLen : newLen
  for (let i = 0; i < len; i++) {
    var leftNode = oldChildren[i]
    var rightNode = newChildren[i]
    index++

    if (!leftNode) {
      if (rightNode) {
        // 舊節點不存在，新節點存在，進行插入操作
        patch = appendPatch(patch, {
          type: PATCH.INSERT,
          vNode: rightNode,
        })
      }
    } else {
      // 相同節點進行比對
      walk(leftNode, rightNode, patches, index)
    }
    if (isVNode(leftNode) && isArray(leftNode.children)) {
      index += leftNode.children.length
    }
  }

  if (sortedSet.moves) {
    // 最后進行重新排序
    patch = appendPatch(patch, {
      type: PATCH.ORDER,
      moves: sortedSet.moves,
    })
  }

  return patch
}

這里首先需要對新的子節點進行重排序，先進行相同節點的 diff ，最后把子節點按照新的子節點順序重新排列。

這里有個較復雜的部分，就是對子節點的重新排序。

function sortChildren(oldChildren, newChildren) {
  // 找出變化后的子節點中帶 key 的 vdom (keys)，和不帶 key 的 vdom (free)
  const newChildIndex = keyIndex(newChildren)
  const newKeys = newChildIndex.keys
  const newFree = newChildIndex.free

  // 所有子節點無 key 不進行對比
  if (newFree.length === newChildren.length) {
    return {
      children: newChildren,
      moves: null,
    }
  }

  // 找出變化前的子節點中帶 key 的 vdom (keys)，和不帶 key 的 vdom (free)
  const oldChildIndex = keyIndex(oldChildren)
  const oldKeys = oldChildIndex.keys
  const oldFree = oldChildIndex.free

  // 所有子節點無 key 不進行對比
  if (oldFree.length === oldChildren.length) {
    return {
      children: newChildren,
      moves: null,
    }
  }

  // O(MAX(N, M)) memory
  const shuffle = []

  const freeCount = newFree.length
  let freeIndex = 0
  let deletedItems = 0

  // 遍歷變化前的子節點，對比變化后子節點的 key 值
  // 并按照對應順序將變化后子節點的索引放入 shuffle 數組中
  for (let i = 0; i < oldChildren.length; i++) {
    const oldItem = oldChildren[i]
    let itemIndex

    if (oldItem.key) {
      if (newKeys.hasOwnProperty(oldItem.key)) {
        // 匹配到變化前節點中存在的 key
        itemIndex = newKeys[oldItem.key]
        shuffle.push(newChildren[itemIndex])
      } else {
        // 移除變化后節點不存在的 key 值
        deletedItems++
        shuffle.push(null)
      }
    } else {
      if (freeIndex < freeCount) {
        // 匹配變化前后的無 key 子節點
        itemIndex = newFree[freeIndex++]
        shuffle.push(newChildren[itemIndex])
      } else {
        // 如果變化后子節點中已經不存在無 key 項
        // 變化前的無 key 項也是多余項，故刪除
        deletedItems++
        shuffle.push(null)
      }
    }
  }

  const lastFreeIndex =
    freeIndex >= newFree.length ? newChildren.length : newFree[freeIndex]

  // 遍歷變化后的子節點，將所有之前不存在的 key 對應的子節點放入 shuffle 數組中
  for (let j = 0; j < newChildren.length; j++) {
    const newItem = newChildren[j]
    if (newItem.key) {
      if (!oldKeys.hasOwnProperty(newItem.key)) {
        // 添加所有新的 key 值對應的子節點
        // 之后還會重新排序，我們會在適當的地方插入新增節點
        shuffle.push(newItem)
      }
    } else if (j >= lastFreeIndex) {
      // 添加剩余的無 key 子節點
      shuffle.push(newItem)
    }
  }

  const simulate = shuffle.slice()
  const removes = []
  const inserts = []
  let simulateIndex = 0
  let simulateItem
  let wantedItem

  for (let k = 0; k < newChildren.length; ) {
    wantedItem = newChildren[k] // 期待元素: 表示變化后 k 的子節點
    simulateItem = simulate[simulateIndex] // 模擬元素: 表示變化前 k 位置的子節點

    // 刪除在變化后不存在的子節點
    while (simulateItem === null && simulate.length) {
      removes.push(remove(simulate, simulateIndex, null))
      simulateItem = simulate[simulateIndex]
    }

    if (!simulateItem || simulateItem.key !== wantedItem.key) {
      // 期待元素的 key 值存在
      if (wantedItem.key) {
        if (simulateItem && simulateItem.key) {
          // 如果一個帶 key 的子元素沒有在合適的位置，則進行移動
          if (newKeys[simulateItem.key] !== k + 1) {
            removes.push(remove(simulate, simulateIndex, simulateItem.key))
            simulateItem = simulate[simulateIndex]
            // if the remove didn"t put the wanted item in place, we need to insert it
            if (!simulateItem || simulateItem.key !== wantedItem.key) {
              inserts.push({ key: wantedItem.key, to: k })
            }
            // items are matching, so skip ahead
            else {
              simulateIndex++
            }
          } else {
            inserts.push({ key: wantedItem.key, to: k })
          }
        } else {
          inserts.push({ key: wantedItem.key, to: k })
        }
        k++
      }
      // 該位置期待元素的 key 值不存在，且模擬元素存在 key 值
      else if (simulateItem && simulateItem.key) {
        // 變化前該位置的元素
        removes.push(remove(simulate, simulateIndex, simulateItem.key))
      }
    } else {
      // 如果期待元素和模擬元素 key 值相等，跳到下一個子節點比對
      simulateIndex++
      k++
    }
  }

  // 移除所有的模擬元素
  while (simulateIndex < simulate.length) {
    simulateItem = simulate[simulateIndex]
    removes.push(
      remove(simulate, simulateIndex, simulateItem && simulateItem.key)
    )
  }

  // 如果只有刪除選項中有值
  // 將操作直接交個 delete patch
  if (removes.length === deletedItems && !inserts.length) {
    return {
      children: shuffle,
      moves: null,
    }
  }

  return {
    children: shuffle,
    moves: {
      removes: removes,
      inserts: inserts,
    },
  }
}


function keyIndex(children) {
  const keys = {}
  const free = []
  const length = children.length

  for (let i = 0; i < length; i++) {
    const child = children[i]

    if (child.key) {
      keys[child.key] = i
    } else {
      free.push(i)
    }
  }

  return {
    keys: keys, // 子節點中所有存在的 key 對應的索引
    free: free, // 子節點中不存在 key 值的索引
  }
}

function remove(arr, index, key) {
  arr.splice(index, 1) // 移除數組中指定元素

  return {
    from: index,
    key: key,
  }
}

這一部分比較復雜，具體可以查看 virtual-dom 的兩個 pr ，這兩個 pr 里面討論了關于 diff 子節點重新排序的優化邏輯。

Rewrite reorder

Rewrite reorder (part 2)

在拿到了 VDOM 的 diff 結果后，需要將得到的 patches 更新到視圖上。

function patch(rootNode, patches) {
  if (!patches || patches.length === 0) return
  // 取得對應 index 的真實 DOM
  const nodes = domIndex(rootNode)
  patches.forEach((patch, index) => {
    patch && applyPatch(nodes[index], patch)
  })
}

function domIndex(rootNode) {
  const nodes = [rootNode]
  const children = rootNode.childNodes
  if (children.length) {
    for (let child of children) {
      if (child.nodeType === 1 || child.nodeType === 3) {
        if (child.nodeType === 1) {
          nodes.push(...domIndex(child))
        } else if (child.nodeType === 3) {
          nodes.push(child)
        }
      }
    }
  }
  return nodes
}

遍歷patches，然后得到每個真實 DOM 和其對應的 patch，然后在真實 DOM 上進行更新：

function applyPatch(node, patchList) {
  for (let patch of patchList) {
    patchOp(node, patch)
  }
}
function patchOp(node, patch) {
  const { type, vNode } = patch
  const parentNode = node.parentNode
  let newNode = null
  switch (type) {
    case PATCH.INSERT:
      // 插入新節點
      break
    case PATCH.REMOVE:
      // 刪除舊新節點
      break
    case PATCH.REPLACE:
      // 替換節點
      break
    case PATCH.ORDER:
      // 子節點重新排序
      break
    case PATCH.VTEXT:
      // 替換文本節點
      break
    case PATCH.PROPS:
      // 更新節點屬性
      break
    default:
      break
  }
}

這里每一步操作，不進行具體展開，感興趣的話可以在我的 github 查看完整代碼。

cito 其他步驟與 virtual-dom 類似，最大的差異點就在子節點的對比上，而且 cito 移除了 patch 更新，在 diff 的過程中，直接更新真實 DOM ，這樣省去了 patch 的存儲，一定程度上節省了內存，后面其他的 VDOM 庫基本使用這種方式。

我們再來看看 cito 在子節點的對比上，到底有何優化？

其實前面我們已經介紹過了，cito 主要變化就是引入了兩端對比，將 diff 算法的速度提升了幾個量級。

/**
 * 子節點對比
 * @param {Element} domNode   父節點的真實DOM
 * @param {Array} oldChildren 舊的子節點
 * @param {Array} children    新的子節點
 */
function updateChildren(domNode, oldChildren, children) {
  const oldChildrenLength = oldChildren.length
  const childrenLength = children.length
  
  let oldEndIndex = oldChildrenLength - 1
  let endIndex = childrenLength - 1
  let oldStartIndex = 0
  let startIndex = 0
  let successful = true
  let nextChild
  
  // 兩端對比算法
  outer: while (
    successful &&
    oldStartIndex <= oldEndIndex &&
    startIndex <= endIndex
  ) {
    successful = false
    let oldStartChild = oldChildren[oldStartIndex]
    let startChild = children[startIndex]
    while (oldStartChild.key === startChild.key) {
      // 子節點對比
      updateNode(oldStartChild, startChild, domNode)
      oldStartIndex++
      startIndex++
      if (oldStartIndex > oldEndIndex || startIndex > endIndex) {
        break outer
      }
      oldStartChild = oldChildren[oldStartIndex]
      startChild = children[startIndex]
      successful = true
    }
    let oldEndChild = oldChildren[oldEndIndex]
    let endChild = children[endIndex]
    while (oldEndChild.key === endChild.key) {
      // 子節點對比
      updateNode(oldEndChild, endChild, domNode)
      oldEndIndex--
      endIndex--
      if (oldStartIndex > oldEndIndex || startIndex > endIndex) {
        break outer
      }
      oldEndChild = oldChildren[oldEndIndex]
      endChild = children[endIndex]
      successful = true
    }

    while (oldStartChild.key === endChild.key) {
      nextChild = endIndex + 1 < childrenLength ? children[endIndex + 1] : null
      // 子節點對比
      updateNode(oldStartChild, endChild, domNode)
      // 移動子節點
      moveChild(domNode, endChild, nextChild)
      oldStartIndex++
      endIndex--
      if (oldStartIndex > oldEndIndex || startIndex > endIndex) {
        break outer
      }
      oldStartChild = oldChildren[oldStartIndex]
      endChild = children[endIndex]
      successful = true
    }
    while (oldEndChild.key === startChild.key) {
      nextChild = oldStartIndex < oldChildrenLength ? oldChildren[oldStartIndex] : null
      // 子節點對比
      updateNode(oldEndChild, startChild, domNode)
      // 移動子節點
      moveChild(domNode, startChild, nextChild)
      oldEndIndex--
      startIndex++
      if (oldStartIndex > oldEndIndex || startIndex > endIndex) {
        break outer
      }
      oldEndChild = oldChildren[oldEndIndex]
      startChild = children[startIndex]
      successful = true
    }
  }
}

子節點對比：

function updateNode(oldNode, node, domParent) {
  if (node === oldNode) {
    return
  }

  const tag = node.tag

  if (oldNode.tag !== tag) {
    // 標簽不一致，創建新節點
    createNode(node, domParent, oldNode, true)
  } else {
    const oldChildren = oldNode.children
    const children = node.children
    const domNode = oldNode.dom
    node.dom = domNode // 真實 DOM 掛在到 虛擬 DOM 上
    // 子節點對比
    if (children !== oldChildren) {
      updateChildren(domNode, node, oldChildren, children)
    }

    const oldProps = oldNode.props
    const props = node.props
    // 屬性對比
    if (props !== oldProps) {
      updateAttributes(domNode, props, oldProps)
    }
  }
}

移動子節點：

function moveChild(domNode, child, nextChild) {
  const domRefChild = nextChild && nextChild.dom
  let domChild = child.dom
  if (domChild !== domRefChild) {
    if (domRefChild) {
      domNode.insertBefore(domChild, domRefChild)
    } else {
      domNode.appendChild(domChild)
    }
  }
}

kivi 的 diff 算法在 cito 的基礎上，引入了最長增長子序列，通過子序列找到最小的 DOM 操作數。

翻譯自 kivi/lib/reconciler.ts

該算法用于找到最小的 DOM 操作數，可以分為以下幾步：

1. 找到數組中首部和尾部公共的節點，并在兩端移動

該方法通過比對兩端的 key 值，找到舊節點（A） 和新節點（B）中索引相同的節點。

  A: -> [a b c d e f g] <-
  B:    [a b f d c g]

這里我們可以跳過首部的 a 和 b，以及尾部的 g。

  A: -> [c d e f] <-
  B:    [f d c]

此時，將嘗試對邊進行比較，如果在對邊有一個 key 值相同的節點，將執行簡單的移動操作，將 c 節點移動到
右邊緣，將 f 節點移動到左邊緣。

  A: -> [d e] <-
  B:    [d]

現在將再次嘗試查找公共的首部與尾部，發現 d 節點是相同的，我們跳過它。

  A: -> [e] <-
  B:    [ ]

然后檢查各個列表的長度是否為0，如果舊節點列表長度為0，將插入新節點列表的剩余節點，或者新節點列表長度為0，將刪除所有舊節點列表中的元素。

這個簡單的算法適用于大多數的實際案例，比如僅僅反轉了列表。

當列表無法利用該算法找到解的時候，會使用下一個算法，例如：

  A: -> [a b c d e f g] <-
  B:    [a c b h f e g]

邊緣的 a 和 g 節點相同，跳過他們。

  A: -> [b c d e f] <-
  B:    [c b h f e]

然后上面的算法行不通了，我們需要進入下一步。

2. 查找需要刪除或者插入的節點，并且某個節點是否需要移動

我們先創建一個數組 P，長度為新子節點列表的長度，并為數組每個元素賦值 -1 ，它表示新子節點應該插入的位置。稍后，我們將把舊子節點中的節點位置分配給這個數組。

  A: [b c d e f]
  B: [c b h f e]
  P: [. . . . .] // . == -1

然后，我們構建一個對象 I，它的鍵表示新子節點的 key 值，值為子節點在剩余節點數組中的位置。

  A: [b c d e f]
  B: [c b h f e]
  P: [. . . . .] // . == -1
  I: {
    c: 0,
    b: 1,
    h: 2,
    f: 3,
    e: 4,
  }
  last = 0

我們開始遍歷舊子節點列表的剩余節點，并檢查是否可以在 I 對象的索引中找到具有相同 key 值的節點。如果找不到任何節點，則將它刪除，否則，我們將節點在舊節點列表位置分配給數組 P。

  A: [b c d e f]
      ^
  B: [c b h f e]
  P: [. 0 . . .] // . == -1
  I: {
    c: 0,
    b: 1, <-
    h: 2,
    f: 3,
    e: 4,
  }
  last = 1

當我們為數組 P 分配節點位置時，我們會保留上一個節點在新子節點列表中的位置，如果當一個節點的位置大于當前節點的位置，那么我們將 moved 變量置為 true。

  A: [b c d e f]
        ^
  B: [c b h f e]
  P: [1 0 . . .] // . == -1
  I: {
    c: 0, <-
    b: 1,
    h: 2,
    f: 3,
    e: 4,
  }
  last = 1 // last > 0; moved = true

上一個節點 b位置為 “1”，當前節點 c 的位置 “0”，所以將 moved 變量置為 true。

  A: [b c d e f]
          ^
  B: [c b h f e]
  P: [1 0 . . .] // . == -1
  I: {
    c: 0,
    b: 1,
    h: 2,
    f: 3,
    e: 4,
  }
  moved = true

對象 I 索引中不存在 d，則刪除該節點

  A: [b c d e f]
            ^
  B: [c b h f e]
  P: [1 0 . . 3] // . == -1
  I: {
    c: 0,
    b: 1,
    h: 2,
    f: 3,
    e: 4, <-
  }
  moved = true

為節點 e 分配位置。

  A: [b c d e f]
              ^
  B: [c b h f e]
  P: [1 0 . 4 3] // . == -1
  I: {
    c: 0,
    b: 1,
    h: 2,
    f: 3, <-
    e: 4,
  }
  moved = true

為節點 f 分配位置。

此時，我們檢查 moved 標志是否被打開，或者舊子節點列表的長度減去已刪除節點的數量不等于新子節點列表的長度。如果其中任何一個條件為真，我們則進入下一步。

3. 如果 moved 為真，查找最小移動數，如果長度發送變化，則插入新節點。

如果 moved 為真，我們需要在 P 數組中找到 最長自增子序列，并移動不屬于這個子序列的所有節點。

  A: [b c d e f]
  B: [c b h f e]
  P: [1 0 . 4 3] // . == -1
  LIS:     [1 4]
  moved = true

現在我們需要同時從尾端遍歷新的子節點列表以及最長自增子序列（后面簡稱 LIS），并檢查當前位置是否等于 LIS 的值。

  A: [b c d e f]
  B: [c b h f e]
              ^  // new_pos == 4
  P: [1 0 . 4 3] // . == -1
  LIS:     [1 4]
              ^  // new_pos == 4
  moved = true

節點 e 保持當前位置

  A: [b c d e f]
  B: [c b h f e]
            ^    // new_pos == 3
  P: [1 0 . 4 3] // . == -1
  LIS:     [1 4]
            ^    // new_pos != 1
  moved = true

移動節點 f，移動到下一個節點 e 前面它。

  A: [b c d e f]
  B: [c b h f e]
          ^      // new_pos == 2
  P: [1 0 . 4 3] // . == -1
          ^      // old_pos == -1
  LIS:     [1 4]
            ^
  moved = true

節點 h 在數組 P 中為 -1 ，則表示插入新節點 h。

  A: [b c d e f]
  B: [c b h f e]
        ^        // new_pos == 1
  P: [1 0 . 4 3] // . == -1
  LIS:     [1 4]
            ^    // new_pos == 1
  moved = true

節點 b 保持當前位置

  A: [b c d e f]
  B: [c b h f e]
      ^          // new_pos == 0
  P: [1 0 . 4 3] // . == -1
  LIS:     [1 4]
          ^      // new_pos != undefined
  moved = true

移動節點 c ，移動到下一個節點 b 前面它。

如果 moved 為 false 時，我們不需要查找LIS，我們只需遍歷新子節點列表，并檢查它在數組 P 中的位置，如果是 -1 ，則插入新節點。

kivi 是作者對虛擬 DOM 性能提升的一些猜想，一開始它就向著性能出發，所有它在實現上代碼可能并不優雅，而且它的 api 也十分不友好。而接下來的 snabbdom 就在 kivi 的基礎上，大大提升了代碼的可讀性，很多講述虛擬 DOM 的文章也將 snabbdom 作為案例。

另外，kivi 的作者也創建了另一個 源碼以及 api 更友好的倉庫：ivi，感興趣可以了解一下。

snabbdom 的優勢就是代碼的可讀性大大提升，并且也引入了兩端對比，diff 速度也不慢。

我們可以簡單看下 snabbdom 的兩端對比算法的核心代碼：

/**
 * 子節點對比
 * @param {Element} parentElm   父節點的真實DOM
 * @param {Array} oldCh 舊的子節點
 * @param {Array} newCh 新的子節點
 */
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
  let idxInOld
  let elmToMove
  let before

  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // 跳過兩端不存在的舊節點
    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]
    }
    /* 
    ** 進行兩端對比，分為四種狀況：
    ** 1. oldStart <=>  newStart
    ** 2. oldEnd   <=>  newEnd
    ** 3. oldStart <=>  newEnd
    ** 4. oldEnd   <=>  newStart
    */
    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)
      insertBefore(parentElm, oldStartVnode.dom, oldEndVnode.dom.nextSibling)
      oldStartVnode = oldCh[++oldStartIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldEndVnode, newStartVnode)) {
      // Vnode moved left
      patchVnode(oldEndVnode, newStartVnode)
      insertBefore(parentElm, oldEndVnode.dom, oldStartVnode.dom)
      oldEndVnode = oldCh[--oldEndIdx]
      newStartVnode = newCh[++newStartIdx]
    } 
    // 上面四種情況都不存在，通過 key 值查找對應 VDOM 進行對比
    else {
      // 構造舊子節點的 map 表 (key => vdom)
      if (oldKeyToIdx === undefined) {
        oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
      }
      idxInOld = oldKeyToIdx[newStartVnode.key]
      // 如果新的子節點在舊子節點不存在，進行插入操作
      if (idxInOld === undefined) {
        insertBefore(parentElm, render(newStartVnode), oldStartVnode.dom)
        newStartVnode = newCh[++newStartIdx]
      }
      // 如果新的子節點在舊子節點存在，進行對比
      else {
        elmToMove = oldCh[idxInOld]
        if (elmToMove.sel !== newStartVnode.sel) {
          // key 值相同，但是 tag 不同，重新生成節點并替換
          insertBefore(parentElm, render(newStartVnode), oldStartVnode.dom)
        } else {
          patchVnode(elmToMove, newStartVnode)
          oldCh[idxInOld] = undefined // 該位置已經對比，進行置空
          insertBefore(parentElm, elmToMove.dom, oldStartVnode.dom)
        }
        newStartVnode = newCh[++newStartIdx]
      }
    }
  }
  // 處理一些未處理到的節點
  if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
    if (oldStartIdx > oldEndIdx) {
      before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].dom
      addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx)
    } else {
      removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
    }
  }
}

關于 snabbdom ，網上有太多教程來分析它的 diff 過程了，不管是虛擬 DOM 的教程，還是 Vue 的源碼分析，這里就不再詳細講述了。但是可以明顯的看到，snabbdom 的 diff 算法是有 cito 和 kivi 的影子在的。

毋庸置疑虛擬 DOM 帶給前端的意義是非凡的，虛擬 DOM 在現如今還有更多新鮮的玩法。
比如 omi 將虛擬 DOM 與 Web Component 的結合，還有 Taro 和 Chameleon 帶來的多端統一的能力。

另外，文中相關的代碼都可以在我的 github 查看，這篇文章更多是對自己學習的一個記錄，如果有什么錯誤的觀點，歡迎進行指正。