虚拟dom算法之snabbdom

[zyl1314]

前言

snabbdom是一个虚拟dom算法库，它的特点是效率高、可扩展，许多开源项目采用了这种算法，例如vue。本文试图还原虚拟dom的diff原理（仅限于snabbdom算法）。

虚拟dom

什么是虚拟dom

首先需要了解什么是虚拟dom，虚拟dom是真实dom的简单映射。我们知道一个真实dom的属性是十分繁多的，但是表示一个真实dom仅仅需要一部分属性就够了。对于一个真实dom，只要我们清楚它的选择器、它的子节点以及它的“数据”（属性、样式、类、事件等），我们就可以利用一个对象（即虚拟dom）来描述这个真实的dom节点，如下：

class Vnode {
    constructor({sel, data, children, text, key}) {
        //  选择器
        this.sel = sel;
        //  key
        this.key = key;
        //  保存属性、样式等
        this.data = data;
        //  子节点
        this.children = children;
        //  对应的真实dom节点
        this.elm = null;
        //  文本节点
        this.text = text;
    }
}

举个例子

<ul>
    <li>a</li>
    <li>b</li>
</ul>

可以被表示为：

new Vnode({
    sel: 'ul',
    children: [
        new Vnode({
            sel: 'li',
            children: [new Vnode({text: a})]
        }),
        new Vnode({
            sel: 'li',
            children: [new Vnode({text: b})]
        })
    ]
})

为什么需要虚拟dom

对于前端mvc模型，当model改变时相应的view需要更新，一种最简单的方法是只要model发生了改变就利用模板引擎更新整个view，这在页面简单时是极好的，但是当面对复杂应用时代价过大，其需要重新渲染dom树，这可是很耗时的。合理的操作是哪里改变了重新渲染哪里，通过比较新旧虚拟dom树可以找出相同和不同，相同的地方就复用真实dom节点，不同的地方就对真实dom节点进行增加、删除、移动等操作，这样一来就大大提高了效率。

虚拟dom的diff

在谈到虚拟dom的diff时有个前提：diff只发生在相同的层级。这是因为跨越层级的dom增添、删除、移动并不常见，一般都是兄弟节点之间的位置发生变化。

首先需要判断两个虚拟节点是否为samaVnode，假如是sameVnode则保留旧的真实dom并对新旧虚拟节点的children进行diff，否则删除掉旧虚拟节点对应的真实dom并替换为新虚拟节点对应的真实dom。如下：

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);
  }
}

sameVnode如下定义：

function sameVnode(vnode1: VNode, vnode2: VNode): boolean {
  return vnode1.key === vnode2.key && vnode1.sel === vnode2.sel;
}

sameVnode需要满足两个条件：

• 选择器相同
• key相同

key的作用可以参考这里：https://cn.vuejs.org/v2/api/#key

新旧虚拟节点children的diff是整个虚拟dom算法的核心，首先解决以下几个特殊情况：

• 新虚拟dom有children，旧虚拟dom没有children

处理方法：假如旧虚拟dom的text属性有定义，说明旧真实dom节点有且仅有文本子节点，需要先清除文本节点，然后将新虚拟节点children对应的真实节点添加到父节点。

// oldVnode  旧虚拟节点
// vnode 新虚拟节点
// oldCh 旧虚拟节点的子虚拟节点
// ch 新虚拟节点的子虚拟节点
// elm 新旧虚拟节点对应的真实节点
} 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);
}

• 旧虚拟dom有children，新虚拟dom没有children

解决方法：删除掉旧虚拟节点children对应的真实节点即可

} else if (isDef(oldCh)) {
  removeVnodes(elm, oldCh as Array<VNode>, 0, (oldCh as Array<VNode>).length - 1);
}

• 旧虚拟节点text属性有定义，新虚拟节点text属性没定义且没有children

解决方法：说明旧节点有且仅有文本子节点，新节点为空节点，删除旧节点文本内容即可

api.setTextContent(elm, '');

• 就虚拟节点的text属性有定义，新虚拟节点的text属性有定义

解决方法：说明新旧节点都有且仅有文本子节点，直接比较文本内容，不相同替换即可

} else if (oldVnode.text !== vnode.text) {
  api.setTextContent(elm, vnode.text as string);
}

以上是新旧虚拟dom子节点的四种特殊情况，还剩下一种普遍情况即：新旧虚拟dom均有children：

if (isDef(oldCh) && isDef(ch)) {
  if (oldCh !== ch) updateChildren(elm, oldCh as Array<VNode>, ch as Array<VNode>, insertedVnodeQueue);
}

各种虚拟dom算法的差别在于updateChildren方法实现的不同，snabbdom算法的特点是给新旧children分别提供了头尾两个指针，diff过程中头尾指针均向中间靠拢，当任一children的头指针超过尾指针则diff过程结束。以下图这个例子做参照，相同字母代表两个虚拟dom是sameVnode：

具体的指针移动方式又可以分为以下6种情况：

• 新children（下文记为ch）的头与旧children（下文记为oldCh）的头是sameVnode

解决方法：这种情况说明oldch头指针指向的虚拟dom的真实节点可原地复用，只需将oldch和ch的头指针分别向后移动一位即可，移动后如下：

• ch的尾与oldCh的尾是sameVnode

解决方法：这种情况说明oldch尾指针指向的虚拟dom的真实节点可原地复用，只需将oldch和ch的尾指针分别向前移动一位即可，移动后如下：

• oldCh的头与ch的尾是sameVnode

解决方法：这种情况说明oldCh头指针指向的虚拟dom的真实节点仍然可以复用，但是其被移动到了oldCh尾指针指向虚拟dom的真实节点的后面，这时需要将oldCh的头指针向后移动一位，ch的尾指针向前移动一位，移动后如下：

• oldCh的尾与ch的头是sameVnode

解决方法：与上面相似，oldCh尾指针指向的虚拟dom的真实节点可以复用，但是其被移动到了oldCh头指针指向虚拟dom的真实节点的前面，这时需要将oldCh的尾指针向前移动一位，ch的头指针向后移动一位，移动后如下：

• 在oldCh中可以找到与ch的头是sameVnode的虚拟节点（此节点记为moveVnode）

解决方法：这种情况意味着moveVnode对应的真实节点可以被复用，且移动到了oldCh头指针指向虚拟dom的真实节点的前面，此时需要将ch的头指针向后移动一位，同时将moveVnode设置为null，因为其已经被复用了，当头指针或者尾指针再指向它时需要跳过。移动后如下：

• 不符合以上五种情况

解决方法：当以上五种情况均不符合时，说明ch头指针指向的虚拟dom是一个全新的节点，也即在oldCh中不能找到可复用的节点，此时应当根据ch头指针指向的虚拟dom创建真实dom，并插入到oldCh头指针指向真实节点的前面。移动后如下：

以上分别对应了6种指针移动的方式，同时可以发现此时ch的头指针已经超越了尾指针，说明diff已经结束，但是此时oldCh的头指针依然小于尾指针，这说明在oldCh头指针和尾指针之间的虚拟dom对应的真实dom不能够被复用，需要删除掉。想象一下，假如oldCh的头指针超越了尾指针，而ch的头指针仍然小于尾指针，这说明了原有的dom节点全部可以复用，且ch的头指针和尾指针之间的虚拟dom代表了新的节点，需要被创建并插入到原有dom中。

下面是snabbdom中updateChildren的代码，添加了部分注释：

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) {
    // 下面4行代码我认为没有意义   不可能出现oldStartVnode或者oldEndVnode为null的情况
    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];
        // key和sel均相同时才是sameVnode
        // 对应上文第五种情况
        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 || newStartIdx <= newEndIdx) {
    // 原节点全部被复用
    if (oldStartIdx > oldEndIdx) {
      before = newCh[newEndIdx+1] == null ? null : newCh[newEndIdx+1].elm;
      addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);
    // 原节点被部分复用
    } else {
      removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
    }
  }
}

---

至此，介绍了sanbbdom算法是如何进行diff的，全文完。