解析 snabbdom 源码 教你实现精简的 Virtual DOM 库

Question

伴随 React 兴起， Virtual DOM 也越来越火，各种各样的实现，各个 UI 库的引入等等。snabbdom 就是 Virtual DOM 的一个简洁实现。不过在解读 snabbdom 之前，首先谈一谈 Virtual DOM 。

什么是 Virtual DOM ？

在谈论 Virtual DOM 之前，必须要理解：什么是 DOM ？

DOM 即 Document Object Model，是一种 通过对象表示结构化文档的方式 。DOM 是跨平台的，也是语言无关的（比如 HTML 和 XML 都可以用它表示与操作）。浏览器处理 DOM 的实现细节，然后我们可以通过 JavaScript 和 CSS 来与它交互。

DOM 的主要问题是没有为创建动态 UI 而优化。

以前直接使用 DOM API 比较繁琐，然后有了 jQuery 等库来简化 DOM 操作；但这没有解决大量 DOM 操作的性能问题。大型页面／单页应用里动态创建／销毁 DOM 很频繁（尤其现在前端渲染的普遍），我们当然可以用各种 trick 来优化性能，但这太痛苦了。

而 Virtual DOM 就是解决问题的一种探索。

Virtual DOM 建立在 DOM 之上，是基于 DOM 的一层抽象，实际可理解为用更轻量的纯 JavaScript 对象（树）描述 DOM（树）。

操作 JavaScript 对象当然比操作 DOM 快，因为不用更新屏幕。我们可以随意改变 Virtual DOM ，然后找出改变再更新到 DOM 上。但要保证高效，需要解决以下问题：

1. 高效的 diff 算法，即两个 Virtual DOM 的比较；
2. 只更新需要更新的 DOM 节点；
3. 数据变化检测，batch DOM 读写操作等等。

带着这些问题，我们进入正题：以 snabbdom 为例，讲讲怎么实现一个 Virtual DOM 库。

snabbdom 总览

snabbdom 的 ES6 改写代码可在 codes/snabbdom 浏览，有 id/className 处理等的小改动，但核心流程完全一致。

代码结构：

src
├── domApi.js    # dom api，主要是各种 DOM 操作的包装，快速浏览即可。
├── export.js    # export，决定暴露什么接口给调用者，可忽略。
├── h.js         # `h()`帮助函数，很简单。
├── index.js     # 核心代码，Virtual DOM 的 diff 实现，从 Virtual DOM 构建 DOM 等等。
├── modules      # 各个模块，主要负责属性处理。
│   ├── class.js
│   ├── props.js
│   └── style.js
├── utils.js     # util 函数。
└── vnode.js     # vnode 定义和一些相关函数。

snabbdom 是轻量的 Virtual DOM 实现，代码量少，模块化，结构清晰。这是我选择 snabbdom 作为源码阅读目标的主要原因。

snabbdom 主要的接口有：

• h(type, data, children)，返回 Virtual DOM 树。
• patch(oldVnode, newVnode)，比较新旧 Virtual DOM 树并更新。

从两个接口开始，下面我们深入讲解 snabbdom 的实现。

snabbdom 的实现

怎么实现 Virtual DOM ？我们首先要定义 Virtual DOM，或者具体点，定义一个 Virtual DOM 节点：vnode。

vnode.js

vnode 是对 DOM 节点的抽象，既然如此，我们很容易定义它的形式：

{
  type, // String，DOM 节点的类型，如 'div'/'span'
  data, // Object，包括 props，style等等 DOM 节点的各种属性
  children // Array，子节点（子 vnode）
}

对应源代码src/vnode.js：

const VNODE_TYPE = Symbol('virtual-node')

function vnode(type, key, data, children, text, elm) {
  const element = {
    __type: VNODE_TYPE,
    type, key, data, children, text, elm
  }

  return element
}
function isVnode(vnode) {
  return vnode && vnode.__type === VNODE_TYPE
}
function isSameVnode(oldVnode, vnode) {
  return oldVnode.key === vnode.key && oldVnode.type === vnode.type
}

代码几乎一眼就懂，有三点注意下：

1. 构造 vnode 时内置了 __type，值为 symbol 。利用 symbol 的唯一性来校验 vnode。
2. vnode 的 children/text 二选一，不可共存。那为什么不把 text 视为 children 的一个元素 ？主要是方便处理，text 节点和其它类型的节点处理起来差异很大。
   1. 可以这样理解，有了 text 代表该 vnode 其实是 VTextNode，仅仅是 snabbdom 没有对 vnode 区分而已。
   2. elm 用于保存 vnode 对应 DOM 节点。
3. isSameVnode 检查两个 vnode 是否 相同。这里的相同是指后一个 vnode 是否由之前的 vnode 变换而来，要求 type 相同且 key 相同：
   1. type 不同，如 div 变到 p，那么 vnode 对应的 DOM 则必须整个替换掉了；
   2. key 不同，那就是不是之前的 vnode 变化来的了，是为不同。

h.js

定义了 vnode 的格式，那么我们可以组合 vnode 得到一颗 Virtual DOM 树了。h 函数就是来帮我们生成虚拟 DOM 树的。源代码 src/h.js：

function h(type, config, ...children) {
  const props = {}
  // 省略用 config 填充 props 的过程
  return vnode(
    type,
    key,
    props,
    flattenArray(children).map(c => {
      return isPrimitive(c) ? vnode(undefined, undefined, undefined, undefined, c) : c
    })
  )
}

如上，有一点可以注意：参数 children 既可以是 Array，也可以是 vnode，甚至是字符串。如果是字符串自动转换成 vnode（该 vnode 的 text 即该字符串）。多数情况下，或者说要有更好的开发体验，我们应该支持 JSX 或类似的语法，然后通过 babel 插件转换成 h 的函数调用。鉴于本文主题是怎么实现 Virtual DOM，这里就不展开了。

index.js

现在进入 snabbdom 的核心，来讲 Virtual DOM 必须实现的两个功能：

1. 怎么从 vnode 创建其对应的 DOM 树？即 Virtual DOM 到真实 DOM。
2. 怎么比较 oldVnode 与 newVnode 两个 vnode，并实现 DOM 树更新？diff 算法应该尽量高效，更新应该尽量复用已有 DOM（最小更新）。

从简单的开始，先讲怎么从 vnode 生成 DOM：

function createElm(vnode, insertedVnodeQueue) {
  let data = vnode.data
  let i
  // 省略 hook 调用
  let children = vnode.children
  let type = vnode.type

  /// 根据 type 来分别生成 DOM
  // 处理 comment
  if (type === 'comment') {
    if (vnode.text == null) {
      vnode.text = ''
    }
    vnode.elm = api.createComment(vnode.text)
  }
  // 处理其它 type
  else if (type) {
    const elm = vnode.elm = data.ns
      ? api.createElementNS(data.ns, type)
      : api.createElement(type)

    // 调用 create hook
    for (let i = 0; i < cbs.create.length; ++i) cbs.create[i](emptyNode, vnode)

    // 分别处理 children 和 text。
    // 这里隐含一个逻辑：vnode 的 children 和 text 不会／应该同时存在。
    if (isArray(children)) {
      // 递归 children，保证 vnode tree 中每个 vnode 都有自己对应的 dom；
      // 即构建 vnode tree 对应的 dom tree。
      children.forEach(ch => {
        ch && api.appendChild(elm, createElm(ch, insertedVnodeQueue))
      })
    }
    else if (isPrimitive(vnode.text)) {
      api.appendChild(elm, api.createTextNode(vnode.text))
    }
    // 调用 create hook；为 insert hook 填充 insertedVnodeQueue。
    i = vnode.data.hook
    if (i) {
      i.create && i.create(emptyNode, vnode)
      i.insert && insertedVnodeQueue.push(vnode)
    }
  }
  // 处理 text（text的 type 是空）
  else {
    vnode.elm = api.createTextNode(vnode.text)
  }

  return vnode.elm
}

上面的代码并不复杂，也不应该复杂，因为 Virtual DOM 是对 DOM 的抽象，是描述，从 Virtual DOM 生成 DOM 本来就应该是直接简明的：根据 type 生成对应的 DOM，把 data 里定义的 各种属性设置到 DOM 上。

当然这里隐藏了一些复杂性，比如 style 处理，比如边缘情况处理等等。接下来讲怎么 diff 两颗 Virtual DOM 树，并执行最小更新。通常情况下，找到两棵任意的树之间最小修改的时间复杂度是 O(n^3)，这不可接受。幸好，我们可以对 Virtual DOM 树有这样的假设：

如果 oldVnode 和 vnode 不同（如 type 从 div 变到 p，或者 key 改变），意味着整个 vnode 被替换（因为我们通常不会去跨层移动 vnode ），所以我们没有必要去比较 vnode 的 子 vnode（children） 了。基于这个假设，我们可以 按照层级分解 树，这大大简化了复杂度，大到接近 O(n) 的复杂度：

此外，对于 children （数组）的比较，因为同层是很可能有移动的，顺
序比较会无法最大化复用已有的 DOM。所以我们通过为每个 vnode 加上 key 来追踪这种顺序变动。

原理分析完，上代码：

function patchVnode(oldVnode, vnode, insertedVnodeQueue) {
  // 因为 vnode 和 oldVnode 是相同的 vnode，所以我们可以复用 oldVnode.elm。
  const elm = vnode.elm = oldVnode.elm
  let oldCh = oldVnode.children
  let ch = vnode.children

  // 如果 oldVnode 和 vnode 是完全相同，说明无需更新，直接返回。
  if (oldVnode === vnode) return

  // 调用 update hook
  if (vnode.data) {
    for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
  }

  // 如果 vnode.text 是 undefined
  if (vnode.text === undefined) {
    // 比较 old children 和 new children，并更新
    if (oldCh && ch) {
      if (oldCh !== ch) {
        // 核心逻辑（最复杂的地方）：怎么比较新旧 children 并更新，对应上面
        // 的数组比较
        updateChildren(elm, oldCh, ch, insertedVnodeQueue)
      }
    }
    // 添加新 children
    else if (ch) {
      // 首先删除原来的 text
      if (oldVnode.text) api.setTextContent(elm, '')
      // 然后添加新 dom（对 ch 中每个 vnode 递归创建 dom 并插入到 elm）
      addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
    }
    // 相反地，如果原来有 children 而现在没有，那么我们要删除 children。
    else if (oldCh) {
      removeVnodes(elm, oldCh, 0, oldCh.length - 1);
    }
    // 最后，如果 oldVnode 有 text，删除。
    else if (oldVnode.text) {
      api.setTextContent(elm, '');
    }
  }
  // 否则 （vnode 有 text），只要 text 不等，更新 dom 的 text。
  else if (oldVnode.text !== vnode.text) {
    api.setTextContent(elm, vnode.text)
  }
}

function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue) {
  let oldStartIdx = 0, 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

  // 遍历 oldCh 和 newCh 来比较和更新
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // 1⃣️ 首先检查 4 种情况，保证 oldStart/oldEnd/newStart/newEnd
    // 这 4 个 vnode 非空，左侧的 vnode 为空就右移下标，右侧的 vnode 为空就左移 下标。
    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]
    }
    /**
     * 2⃣️ 然后 oldStartVnode/oldEndVnode/newStartVnode/newEndVnode 两两比较，
     * 对有相同 vnode 的 4 种情况执行对应的 patch 逻辑。
     * - 如果同 start 或同 end 的两个 vnode 是相同的（情况 1 和 2），
     *   说明不用移动实际 dom，直接更新 dom 属性／children 即可；
     * - 如果 start 和 end 两个 vnode 相同（情况 3 和 4），
     *   那说明发生了 vnode 的移动，同理我们也要移动 dom。
     */
    // 1. 如果 oldStartVnode 和 newStartVnode 相同（key相同），执行 patch
    else if (isSameVnode(oldStartVnode, newStartVnode)) {
      // 不需要移动 dom
      patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
      oldStartVnode = oldCh[++oldStartIdx]
      newStartVnode = newCh[++newStartIdx]
    }
    // 2. 如果 oldEndVnode 和 newEndVnode 相同，执行 patch
    else if (isSameVnode(oldEndVnode, newEndVnode)) {
      // 不需要移动 dom
      patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
      oldEndVnode = oldCh[--oldEndIdx]
      newEndVnode = newCh[--newEndIdx]
    }
    // 3. 如果 oldStartVnode 和 newEndVnode 相同，执行 patch
    else if (isSameVnode(oldStartVnode, newEndVnode)) {
      patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
      // 把获得更新后的 (oldStartVnode/newEndVnode) 的 dom 右移，移动到
      // oldEndVnode 对应的 dom 的右边。为什么这么右移？
      // （1）oldStartVnode 和 newEndVnode 相同，显然是 vnode 右移了。
      // （2）若 while 循环刚开始，那移到 oldEndVnode.elm 右边就是最右边，是合理的；
      // （3）若循环不是刚开始，因为比较过程是两头向中间，那么两头的 dom 的位置已经是
      //     合理的了，移动到 oldEndVnode.elm 右边是正确的位置；
      // （4）记住，oldVnode 和 vnode 是相同的才 patch，且 oldVnode 自己对应的 dom
      //     总是已经存在的，vnode 的 dom 是不存在的，直接复用 oldVnode 对应的 dom。
      api.insertBefore(parentElm, oldStartVnode.elm, api.nextSibling(oldEndVnode.elm))
      oldStartVnode = oldCh[++oldStartIdx]
      newEndVnode = newCh[--newEndIdx]
    }
    // 4. 如果 oldEndVnode 和 newStartVnode 相同，执行 patch
    else if (isSameVnode(oldEndVnode, newStartVnode)) {
      patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
      // 这里是左移更新后的 dom，原因参考上面的右移。
      api.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
      oldEndVnode = oldCh[--oldEndIdx]
      newStartVnode = newCh[++newStartIdx]
    }

    // 3⃣️ 最后一种情况：4 个 vnode 都不相同，那么我们就要
    // 1. 从 oldCh 数组建立 key --> index 的 map。
    // 2. 只处理 newStartVnode （简化逻辑，有循环我们最终还是会处理到所有 vnode），
    //    以它的 key 从上面的 map 里拿到 index；
    // 3. 如果 index 存在，那么说明有对应的 old vnode，patch 就好了；
    // 4. 如果 index 不存在，那么说明 newStartVnode 是全新的 vnode，直接
    //    创建对应的 dom 并插入。
    else {
      // 如果 oldKeyToIdx 不存在，创建 old children 中 vnode 的 key 到 index 的
      // 映射，方便我们之后通过 key 去拿下标。
      if (oldKeyToIdx === undefined) {
        oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
      }
      // 尝试通过 newStartVnode 的 key 去拿下标
      idxInOld = oldKeyToIdx[newStartVnode.key]
      // 下标不存在，说明 newStartVnode 是全新的 vnode。
      if (idxInOld == null) {
        // 那么为 newStartVnode 创建 dom 并插入到 oldStartVnode.elm 的前面。
        api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm)
        newStartVnode = newCh[++newStartIdx]
      }
      // 下标存在，说明 old children 中有相同 key 的 vnode，
      else {
        elmToMove = oldCh[idxInOld]
        // 如果 type 不同，没办法，只能创建新 dom；
        if (elmToMove.type !== newStartVnode.type) {
          api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm)
        }
        // type 相同（且key相同），那么说明是相同的 vnode，执行 patch。
        else {
          patchVnode(elmToMove, newStartVnode, insertedVnodeQueue)
          oldCh[idxInOld] = undefined
          api.insertBefore(parentElm, elmToMove.elm, oldStartVnode.elm)
        }
        newStartVnode = newCh[++newStartIdx]
      }
    }
  }

  // 上面的循环结束后（循环条件有两个），处理可能的未处理到的 vnode。
  // 如果是 new vnodes 里有未处理的（oldStartIdx > oldEndIdx
  // 说明 old vnodes 先处理完毕）
  if (oldStartIdx > oldEndIdx) {
    before = newCh[newEndIdx+1] == null ? null : newCh[newEndIdx+1].elm
    addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
  }
  // 相反，如果 old vnodes 有未处理的，删除 （为处理 vnodes 对应的） 多余的 dom。
  else if (newStartIdx > newEndIdx) {
    removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
  }
}

到这里讲完了 snabbdom 的核心实现，可以发现，Virtual DOM 比我们想的会简单一点。本篇限于篇幅，代码肯定不会贴全，想看完整代码的可以去官方或者我用 ES6 改写的仓库。

Answer 1

@qiangzi7723

Answer 2

嗯嗯，感谢，看明白了。发现了个小问题，关于while循环的2⃣️.4小点里面的

    // 4. 如果 oldEndVnode 和 newStartVnode 相同，执行 patch
    else if (isSameVnode(oldEndVnode, newStartVnode)) {
      patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
      // 这里是左移更新后的 dom，原因参考上面的右移。
      api.insertBefore(parentElm, oldEndVnode.elm, api.nextSibling(oldStartVnode.elm))
      oldEndVnode = oldCh[--oldEndIdx]
      newStartVnode = newCh[++newStartIdx]
    }

这里面的insertBefore应该不需要nextSibling了，直接插到oldStartVnode前面才对。

Answer 3

@qiangzi7723 文章里其实已经写了，如果希望更多阅读，可以参考：

1. https://calendar.perfplanet.com/2013/diff/
2. https://zhuanlan.zhihu.com/p/20346379

为什么一次循环里比较 4 个 vnode？但你可以看到如果 isSameVnode 通过才会处理相应的两个 vnode，然后进入下次循环：

1. isSameVnode 判断通过说明是新旧队列里的相同的 vnode，当然要做移动／更新处理。
2. 一次虽然 4 个 vnode 俩俩比较，但最终只处理一对 vnode，对不对？
3. 如果 isSameVnode 判断都没通过，其实只处理 newStartVnode，要么从旧队列里找到它对应的 vnode 做更新处理，找不到则当作新插入的 vnode 处理。

所以整体逻辑是清晰的。

Answer 4

你好，我想问下关于snabbdom里面的

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {

这一部分通过比较头尾节点是否相同从而达到diff比较的算法的具体原理是什么？为什么可以这样做的呢？在算法上有相关的学名吗？