前言

DOM是很慢的。真正的 DOM 元素非常庞大，这是因为标准就是这么设计的。而且操作它们的时候你要小心翼翼，轻微的触碰可能就会导致页面重排产生回流重绘，这可是杀死性能的罪魁祸首。

Virtual Dom的原理是用 JavaScript 对象表示 DOM 信息和结构，当状态变更的时候，重新渲染这个 JavaScript 的对象结构。然后通过新渲染的对象树去和旧的树进行对比使用一个diff算法计算差异，记录下来的不同就是我们需要对页面真正的 DOM 操作，然后把它们应用在真正的 DOM 树上，从而减少了页面的回流和重绘次数。

image.png

Vue选择的virtual dom库是snabbdom，本文是对这个库的源代码进行解析，核心会放在diff算法上。

代码

项目地址：snabbdom
代码是typescript，不过我解析的时候会说一些补充的东西让读者不会出现因为是typescript所以看不懂的情况。

解析

解析我会从三个大方向上来说，第一个是js模拟的dom节点vnode的结构，第二个是diff算法，第三个是有了diff如何打patch的。

vnode结构(用JS对象模拟DOM树)

vnode的定义在项目中src文件夹的vnode.ts上

import {Hooks} from './hooks';
import {AttachData} from './helpers/attachto'
import {VNodeStyle} from './modules/style'
import {On} from './modules/eventlisteners'
import {Attrs} from './modules/attributes'
import {Classes} from './modules/class'
import {Props} from './modules/props'
import {Dataset} from './modules/dataset'
import {Hero} from './modules/hero'

export type Key = string | number;

export interface VNode {
  sel: string | undefined;
  data: VNodeData | undefined;
  children: Array<VNode | string> | undefined;
  elm: Node | undefined;
  text: string | undefined;
  key: Key | undefined;
}

export interface VNodeData {
  props?: Props;
  attrs?: Attrs;
  class?: Classes;
  style?: VNodeStyle;
  dataset?: Dataset;
  on?: On;
  hero?: Hero;
  attachData?: AttachData;
  hook?: Hooks;
  key?: Key;
  ns?: string; // for SVGs
  fn?: () => VNode; // for thunks
  args?: Array<any>; // for thunks
  [key: string]: any; // for any other 3rd party module
}

export function vnode(sel: string | undefined,
                      data: any | undefined,
                      children: Array<VNode | string> | undefined,
                      text: string | undefined,
                      elm: Element | Text | undefined): VNode {
  let key = data === undefined ? undefined : data.key;
  return {sel: sel, data: data, children: children,
          text: text, elm: elm, key: key};
}

export default vnode;

代码中定义了两个interface，VNode和VNodeData，暴露了一个vnode的构造函数

vnode对象属性

vnode对象有6个属性
sel 可以是custom tag,可以是'div','span',etc,代表这个virtual dom的tag name
data, virtual dom数据,它们与dom element的prop、attr的语义类似。但是virtual dom包含的数据可以更灵活。比如利用./modules/class.js插件,我们在data里面轻松toggle一个类名h('p', {class: {'hide': hideIntro}})
children, 对应element的children,但是这是vdom的children。vdom的实现重点就在对children的patch上
text, 对应element.textContent,在children里定义一个string,那么我们会为这个string创建一个textNode
elm, 对dom element的引用
key 用于提示children patch过程,随后面详细说明

vnode的创建与渲染

在接下来的说明之前先介绍一个豆知识，在vue文档中，同时在这个snabbdom中我们都会看到有个h函数，这个函数我之前一直没理解是什么意思。

wthat is 'h'
It comes from the term "hyperscript", which is commonly used in many virtual-dom implementations. "Hyperscript" itself stands for "script that generates HTML structures" because HTML is the acronym for "hyper-text markup language".
所以基本上h函数的意义差不多就是createElement的意思
在snabbdom里面h函数创建一个vnode并返回，具体实现就不细说了

diff算法(patch)

之前我们在snabbdom的事例里面看到

var snabbdom = require('snabbdom');
var patch = snabbdom.init([ // Init patch function with chosen modules
  require('snabbdom/modules/class').default, // makes it easy to toggle classes
  require('snabbdom/modules/props').default, // for setting properties on DOM elements
  require('snabbdom/modules/style').default, // handles styling on elements with support for animations
  require('snabbdom/modules/eventlisteners').default, // attaches event listeners
]);
var h = require('snabbdom/h').default; // helper function for creating vnodes

var container = document.getElementById('container');

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!')
]);
// Patch into empty DOM element – this modifies the DOM as a side effect
patch(container, vnode);

var newVnode = h('div#container.two.classes', {on: {click: anotherEventHandler}}, [
  h('span', {style: {fontWeight: 'normal', fontStyle: 'italic'}}, 'This is now italic type'),
  ' and this is still just normal text',
  h('a', {props: {href: '/bar'}}, 'I\'ll take you places!')
]);
// Second `patch` invocation
patch(vnode, newVnode); // Snabbdom efficiently updates the old view to the new state

可以看到patch函数是snabbdom.init出来的，而且传入的参数既可以是用h函数返回的一个vnode又可以是实际的dom元素，现在我们看看init方法的代码，一些实现钩子之类的代码我们就不看了

  // snabbdom的init方法
  ...
export function init(modules: Array<Partial<Module>>, domApi?: DOMAPI) {
  ...
  return function patch(oldVnode: VNode | Element, vnode: VNode): VNode {
    let i: number, elm: Node, parent: Node;
    const insertedVnodeQueue: VNodeQueue = [];
    for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]();

    if (!isVnode(oldVnode)) {
      oldVnode = emptyNodeAt(oldVnode);
    }

    if (sameVnode(oldVnode, vnode)) {
      patchVnode(oldVnode, vnode, insertedVnodeQueue);
    } else {
      elm = oldVnode.elm as Node;
      parent = api.parentNode(elm);

      createElm(vnode, insertedVnodeQueue);

      if (parent !== null) {
        api.insertBefore(parent, vnode.elm as Node, api.nextSibling(elm));
        removeVnodes(parent, [oldVnode], 0, 0);
      }
    }

    for (i = 0; i < insertedVnodeQueue.length; ++i) {
      (((insertedVnodeQueue[i].data as VNodeData).hook as Hooks).insert as any)(insertedVnodeQueue[i]);
    }
    for (i = 0; i < cbs.post.length; ++i) cbs.post[i]();
    return vnode;
  };
}

先会传入一个modules，就是一个模组，这些模组会在一些阶段加一些钩子，以此实现一个模组功能。说到模组功能我就想起了chartjs的模组。模组为第三方开发者提供了个扩展程序的一个接口，在chartjs里面它使用的是观察者模式，在一开始会register各个模组，通过在图表创建，更新，销毁等地方写了notify来通知各个模组，以此实现了一个模组功能。

回归patch，我们它会先判断是不是sameVnode(通过vnode的key和sel属性是不是一样的来判断)，如果原来不是同一个key的vnode的话那就没必要用什么diff了，只能直接创建一个新元素。这里我们专注于看如果是同一key同一sel下的vnode发送了某些变化之后怎么进行patch操作。

// patchVnode函数
function patchVnode(oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) {
  let i: any, hook: any;
  ... prepatch的钩子我也删了
  const elm = vnode.elm = (oldVnode.elm as Node);
  let oldCh = oldVnode.children;
  let ch = vnode.children;
  if (oldVnode === vnode) return;
  ...update的钩子，我删了
  if (isUndef(vnode.text)) {
    if (isDef(oldCh) && isDef(ch)) {
      if (oldCh !== ch) updateChildren(elm, oldCh as Array<VNode>, ch as Array<VNode>, insertedVnodeQueue);
    } else if (isDef(ch)) {
      if (isDef(oldVnode.text)) api.setTextContent(elm, '');
      addVnodes(elm, null, ch as Array<VNode>, 0, (ch as Array<VNode>).length - 1, insertedVnodeQueue);
    } else if (isDef(oldCh)) {
      removeVnodes(elm, oldCh as Array<VNode>, 0, (oldCh as Array<VNode>).length - 1);
    } else if (isDef(oldVnode.text)) {
      api.setTextContent(elm, '');
    }
  } else if (oldVnode.text !== vnode.text) {
    api.setTextContent(elm, vnode.text as string);
  }
  ... postpatch钩子
}

可以看到主要逻辑里面先做了isUndef(vnode.text)的判断，因为如果不是文本节点的话是不会有这个属性的，如果是文本节点直接setTextContent就行了，如果不是的话我们还要继续看。
在vnode不是文本节点的时候做了四个判断
前三个是判断vnode和oldVnode是不是都有儿子，或者一个有一个没有。
第一种情况如果都有儿子的话会调用updateChildren然后递归的调用patchVnode函数。
第二种情况vnode有儿子而oldVnode没有，那差异就可以直接调用addVnodes在DOM上插入儿子并更新insertedVnodeQueue记录了。
第三种情况是vnode没有儿子而oldVnode有，说明差异是儿子的移除，直接调用removeVnodes在DOM上移除儿子并更新insertedVnodeQueue。
第四种情况就是这个节点是个文本节点，然后差异是oldVnode有text，vnode没有了，直接调用setTextContent设置值为空

比较核心的还是前后vnode都有孩子的情况也就是updateChildren里面，在进updateChildren函数之前我还有一点想说的。
两个树的完全的 diff 算法是一个时间复杂度为 O(n^3) 的问题。但是在前端当中，你很少会跨越层级地移动DOM元素。所以 Virtual DOM 只会对同一个层级的元素进行对比：

image.png

updateChildren更新儿子

这段逻辑是主要的diff算法部分，有点复杂，我看了2个多小时还结合其他资料才理解为什么要这样写。
先贴一下代码

  function updateChildren(parentElm: Node,
                          oldCh: Array<VNode>,
                          newCh: Array<VNode>,
                          insertedVnodeQueue: VNodeQueue) {
    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: any;
    let idxInOld: number;
    let elmToMove: VNode;
    let before: any;

    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (oldStartVnode == null) {
        oldStartVnode = oldCh[++oldStartIdx]; // Vnode might have been moved left
      } 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, insertedVnodeQueue);
        oldStartVnode = oldCh[++oldStartIdx];
        newStartVnode = newCh[++newStartIdx];
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
        oldEndVnode = oldCh[--oldEndIdx];
        newEndVnode = newCh[--newEndIdx];
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
        api.insertBefore(parentElm, oldStartVnode.elm as Node, api.nextSibling(oldEndVnode.elm as Node));
        oldStartVnode = oldCh[++oldStartIdx];
        newEndVnode = newCh[--newEndIdx];
      } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
        api.insertBefore(parentElm, oldEndVnode.elm as Node, oldStartVnode.elm as Node);
        oldEndVnode = oldCh[--oldEndIdx];
        newStartVnode = newCh[++newStartIdx];
      } else {
        if (oldKeyToIdx === undefined) {
          oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
        }
        idxInOld = oldKeyToIdx[newStartVnode.key as string];
        if (isUndef(idxInOld)) { // New element
          api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm as Node);
          newStartVnode = newCh[++newStartIdx];
        } else {
          elmToMove = oldCh[idxInOld];
          if (elmToMove.sel !== newStartVnode.sel) {
            api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm as Node);
          } else {
            patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
            oldCh[idxInOld] = undefined as any;
            api.insertBefore(parentElm, (elmToMove.elm as Node), oldStartVnode.elm as Node);
          }
          newStartVnode = newCh[++newStartIdx];
        }
      }
    }
    if (oldStartIdx > oldEndIdx) {
      before = newCh[newEndIdx+1] == null ? null : newCh[newEndIdx+1].elm;
      addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);
    } else if (newStartIdx > newEndIdx) {
      removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
    }
  }

我开始阅读的时候主要的疑惑点就是这一大坨if else，我们先来考虑一下以下几种情况
newVnode 5 1 2 3 4
oldVnode 1 2 3 4 5
在代码中首先会进入
else if (sameVnode(oldEndVnode, newStartVnode))
会先递归调用patchNode对这个子vnode打patch
然后把例子中oldVnode的5插入到1前面

       } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
        api.insertBefore(parentElm, oldEndVnode.elm as Node, oldStartVnode.elm as Node);
        oldEndVnode = oldCh[--oldEndIdx];
        newStartVnode = newCh[++newStartIdx];
      }

有了个例子之后我们看一下我盗的几个图，实际的DOM操作只有下面三种情况

image.png

上面这种情况的例子是
newVnode 0 2 3 1
oldVnode 0 1 2 3

      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
        api.insertBefore(parentElm, oldStartVnode.elm as Node, api.nextSibling(oldEndVnode.elm as Node));
        oldStartVnode = oldCh[++oldStartIdx];
        newEndVnode = newCh[--newEndIdx];
      }

image.png

上面这种情况就是我之前举的例子
newVnode 0 3 12
oldVnode 0 1 2 3
对应代码

      } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
        api.insertBefore(parentElm, oldEndVnode.elm as Node, oldStartVnode.elm as Node);
        oldEndVnode = oldCh[--oldEndIdx];
        newStartVnode = newCh[++newStartIdx];
      }

image.png

上面的情况的例子是newVnode里面的节点oldVnode里面没有
newVnode 0 x 1 2 3
oldVnode 0 1 2 3
对应代码

       else {
        // 这一块不用在意，这只是一个根据key去找index的表
        if (oldKeyToIdx === undefined) {
          oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
        }
        // 看看当前newStartVnode在不在oldVnode里面
        idxInOld = oldKeyToIdx[newStartVnode.key as string];
        // 这里就是图中所示插入新节点到dom
        if (isUndef(idxInOld)) { // New element
          api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm as Node);
          newStartVnode = newCh[++newStartIdx];
        } else {
          // 如果在newStartVnode在oldVnode中，
          elmToMove = oldCh[idxInOld];
          // 如果已经不是一个vnode的东西了，直接新建节点插入到old头探针之前
          if (elmToMove.sel !== newStartVnode.sel) {
            api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm as Node);
          } else {
            // 如果这个vnode还能抢救，递归调用patchVnode，把对应的elmToMove插入到old头探针之前
            patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
            oldCh[idxInOld] = undefined as any;
            api.insertBefore(parentElm, (elmToMove.elm as Node), oldStartVnode.elm as Node);
          }
          newStartVnode = newCh[++newStartIdx];
        }
      }

结束的时候，也就是当oldVnode或者newVnode有一个遍历完的时候

image.png

如上图，如果是old先遍历完，则剩余的new里面的肯定要插进来啊
对应代码

    if (oldStartIdx > oldEndIdx) {
      before = newCh[newEndIdx+1] == null ? null : newCh[newEndIdx+1].elm;
      addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);
    }

image.png

同理，如果new先遍历完，说明old里面有些元素要被移除
对应代码

    else if (newStartIdx > newEndIdx) {
      removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
    }

到此最麻烦的updateChildren就算解析完了。