浅析 Snabbdom 中 vnode 和 diff 算法

发表于 2年以前 | 总阅读数：363 次

一、一些必要的概念解释

1、什么是虚拟 DOM

目前前端使用最多的就是 vue 或 react 了，我们在学习这两个框架的过程中，总有一个绕不开的话题：vnode，也就是虚拟 DOM。什么是虚拟 DOM，引用一段 vue 官方的解释就是：

“一个用 JavaScript 生成名为 Virtual Dom 的 DOM 副本。

也就是说，虚拟 DOM 只是一个普通的 js 对象。我们都知道，对于 DOM 频繁的进行增删改查，成本很高，既然虚拟 DOM 只是一个 js 对象，那我们用操作对象的方式来代替操作 DOM，最后一次性的更改 DOM，那么一定程度上就能使得我们的 UI 更新更高效。

2、什么是 diff 算法

既然虚拟 DOM 的最终任务就是用计算出来的结果来修改 DOM，那么更新 DOM 还是不更新 DOM，怎么更新 DOM。这就需要借助 diff 算法来给出最终答案。

“diff 算法是用来计算新老 DOM 之间差异性的一种计算算法。

3、Snabbdom 是什么

“Snabbdom 是一个虚拟 DOM 库，专注提供简单、模块性的体验，以及强大的功能和性能。

可能很多人都没听说过这个库，其实 vue 中虚拟 DOM 这一块就是借鉴的 Snabbdom，但是，它相比 vue 更加简单和纯粹，所以学习 Snabbdom 也能帮助我们理解 vue 中虚拟 DOM 相关的知识。

二、Snabbdom 中 diff 算法的源码解析

1、Snabbdom 的使用

下面先来看看 Snabbdom 的简单的使用

import {
  init,
  classModule,
  propsModule,
  styleModule,
  eventListenersModule,
  h,
} from "snabbdom";

const patch = init([
  // Init patch function with chosen modules
  classModule, // makes it easy to toggle classes
  propsModule, // for setting properties on DOM elements
  styleModule, // handles styling on elements with support for animations
  eventListenersModule, // attaches event listeners
]);
// 创建一个 vnode
var vnode = h('div#container.two.classes', {on: {click: someFn}}, [
  h('span', {style: {fontWeight: 'bold'}}, '这只是普通文本'),
  ' and this is just normal text',
  h('a', {props: {href: '/foo'}}, '这是一个链接!')
]);
// 选择容器
var container = document.getElementById('container');
// 将 vnode patch 到容器中
patch(container, vnode);
// 生成一个新的 vnode
var newVnode = h('div#container.two.classes', {on: {click: anotherEventHandler}}, [
  h('span', {style: {fontWeight: 'normal', fontStyle: 'italic'}}, '现在是斜体类型文本'),
  ' and this is still just normal text',
  h('a', {props: {href: '/bar'}}, '这是一个链接!')
]);
// 用新 DOM 替换老 DOM
patch(vnode, newVnode);

上面的 demo 演示的流程就是：首先创建一个 vnode，patch 到选择的容器中，然后再创建一个新的 vnode，用老的 vnode 去替换新的 vnode。这里要注意的是，patch 方法的第一个参数，可以是一个 vnode 类型，也可以是一个 Element 类型，下面会介绍对这两种参数类型的处理。

其实上面这种初始化容器中的 DOM 和新老 DOM 的替换，我们在使用 vue 的过程，也是大量用到的，只不过 vue 替我们解决了繁琐的计算过程。

2、vnode 的生成过程

首先我们先来看看 vnode 生成过程，也就是下面这一块：

var vnode = h('div#container.two.classes', {on: {click: someFn}}, [
  h('span', {style: {fontWeight: 'bold'}}, '这是加粗的类型'),
  ' and this is just normal text',
  h('a', {props: {href: '/foo'}}, '这是一个链接!')
]);

上面的核心点就是 h 函数，它接受三个参数，第一个是标签，第二个是属性，第三个是子节点，其中子节点也可以是一个 h 函数的返回值。

下面贴上 h 函数的源码：

export function h(sel: any, b?: any, c?: any): VNode {
  let data: VNodeData = {};
  let children: any;
  let text: any;
  let i: number;
  if (c !== undefined) {
    if (b !== null) {
      data = b;
    }
    if (is.array(c)) {
      children = c;
    } else if (is.primitive(c)) {
      text = c.toString();
    } else if (c && c.sel) {
      children = [c];
    }
  } else if (b !== undefined && b !== null) {
    // c 是 undefined，b 有可能是 children 类型
    if (is.array(b)) {
      children = b;
    } else if (is.primitive(b)) {
      text = b.toString();
    } else if (b && b.sel) {
      children = [b];
    } else {
      data = b;
    }
  }
  if (children !== undefined) {
    for (i = 0; i < children.length; ++i) {
      // 这里 children 有可能是一个 h 函数的返回值，也有可能是一个 text 文本
      if (is.primitive(children[i])) 
        children[i] = vnode(
          undefined,
          undefined,
          undefined,
          children[i],
          undefined
        );
    }
  }
  // 对于 svg 标签的处理
  if (
    sel[0] === "s" &&
    sel[1] === "v" &&
    sel[2] === "g" &&
    (sel.length === 3 || sel[3] === "." || sel[3] === "#")
  ) {
    addNS(data, children, sel);
  }
  return vnode(sel, data, children, text, undefined);
}

上面这段代码首先是做了一些函数传参的处理，它允许传入的参数更加灵活。其次，调用 vnode 方法生成生成子节点的 vnode 和自己本身的 vnode，下面再接着看一下 vnode 函数的实现逻辑。

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

vnode 函数的实现的函数很简单，就是返回一个 js 对象，所以本质上一个 vnode 就是一个如下结构的 js 对象。

{
  sel: string | undefined;
  data: any | undefined;
  children: Array<VNode | string> | undefined,
  text: string | undefined,
  elm: Element | Text | undefined,
  key: string | undefined
}

每一个 children 也可能是一个 vnode，这样就组装成了一个 vnode 树形结构。

3、patch 过程

了解完了 vnode 的生成过程，我们接下来就是将 vnode patch 到容器中，也就是下面的这两段代码。

patch(container, vnode); // 将 vnode patch 到容器中

和

patch(vnode, newVnode); // 用新 DOM 替换老 DOM

patch 函数其实就是 init 方法的返回值，所以找到 init 的源码：

export function init(modules: Array<Partial<Module>>, domApi?: DOMAPI) {  
  // dom 操作 api
  const api: DOMAPI = domApi !== undefined ? domApi : htmlDomApi;

  function emptyNodeAt() {}

  function createRmCb() {}

  // 根据 vnode 创建一个 dom 树
  function createElm() {}

  function addVnodes() {}

  function invokeDestroyHook() {}

  function removeVnodes() {}

  function updateChildren() {}

  function patchVnode() {}

  return function patch(oldVnode: VNode | Element, vnode: VNode): VNode {
    let elm: Node, parent: Node;

    // 如果不是 vnode(第一次调用 patch 时)，
    // 那么就是 Element 类型，直接创建一个空对象
    // 空对象的 elm 值等于 oldVnode
    if (!isVnode(oldVnode)) {
      oldVnode = emptyNodeAt(oldVnode);
    }
     // 如果满足 sameVnode
    if (sameVnode(oldVnode, vnode)) {
      patchVnode(oldVnode, vnode, insertedVnodeQueue);
    } else {
      elm = oldVnode.elm!;
      parent = api.parentNode(elm) as Node;

      createElm(vnode);

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

这里有一部分关于 hooks 的执行时机的代码，由于本文主要是研究 diff 过程的，所以关于 hooks 的执行逻辑，代码中就没有贴进来了，感兴趣的同学可以研究下官方的源码。可以看到上面的代码就是返回 patch 函数，当我们调用 patch(container, vnode) 或 patch(vnode, newVnode) 的时候，就会执行该方法；

再看一下 patch 函数的实现逻辑：

1、对 vnode，也就是第一个参数类型做了判断，因为 vnode 有可能是一个 VNode 实例，也有可能是一个 Element 实例。

2、比较新老节点的根节点是否相同，这里比较逻辑的是判断新老节点的 key、sel 和 data.is 这三者都相等，才认为相同。

function sameVnode(vnode1: VNode, vnode2: VNode): boolean {
  const isSameKey = vnode1.key === vnode2.key;
  const isSameIs = vnode1.data?.is === vnode2.data?.is;
  const isSameSel = vnode1.sel === vnode2.sel;
  return isSameSel && isSameKey && isSameIs;
}

3、相同的逻辑我们先跳过，先看 sameVnode(oldVnode, vnode) 返回 false 的情况。先调用 createElm(vnode, insertedVnodeQueue) 创建 DOM 树，然后再将新创建的 DOM 树直接 append 到容器的父节点下，直接替换子节点。

最后，为了帮助大家理解整个 patch 的过程，我用一张图来描述这个过程：

4、新老节点的 diff

上面 patch 函数的实现逻辑中，当 sameVnode(oldVnode, vnode) 返回 true 时，会执行 patchVnode 方法，patchVnode 其实就是用来比较新老节点的差异，计算出一个新的节点的。一起来看看 patchVnode 的比较实现：

function patchVnode(
    oldVnode: VNode,
    vnode: VNode,
    insertedVnodeQueue: VNodeQueue
  ) {

    const elm = (vnode.elm = oldVnode.elm)!;
    const oldCh = oldVnode.children as VNode[];
    const ch = vnode.children as VNode[];
    // 如果新老节点相等，则不用替换
    if (oldVnode === vnode) return;

    // 如果新节点的子节点不是 textNode 类型。
    if (isUndef(vnode.text)) {
      if (isDef(oldCh) && isDef(ch)) {
        // 如果新节点的子节点类型和老节点的子节点类型都是 children 类型
        if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue);
      } else if (isDef(ch)) {
        // 如果新节点的子节点类型是 children 类型，老节点的类型是 text 类型
        if (isDef(oldVnode.text)) api.setTextContent(elm, "");
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
      } else if (isDef(oldCh)) {
        // 如果老节点的子节点类型是 children 类型，新节点没有子节点
        removeVnodes(elm, oldCh, 0, oldCh.length - 1);
      } else if (isDef(oldVnode.text)) { 
        // 如果老节点的子节点类型是 text 类型，新节点没有子节点
        api.setTextContent(elm, "");
      }
    } else if (oldVnode.text !== vnode.text) { 
      // 如果新节点的子节点是 text 类型。
      if (isDef(oldCh)) {
        removeVnodes(elm, oldCh, 0, oldCh.length - 1);
      }
      api.setTextContent(elm, vnode.text!);
    }
  }

这里首先是判断 oldVnode 与 vnode 是否相等，如果相等，那就不用继续比较了；如果不相等，先执行新节点的 update 生命周期。因为根节点通过 sameVnode 方法比较过后， Snabbdom 就认为 vnode 和 oldVnode 的根节点是相等的，就不用更新根节点了。所以接下来就直接处理子节点的更新，这里为了方便大家理解，我先放一张子节点的比较的流程图。

上面我们在生成 vnode 的时候，根据节点类型，分别给 text 和 children 的值做了计算。所以，一个 vnode 的子节点 text 和 children 属性不可能同时有值。所以根据流程图，子节点对比的过程如下：

1、新节点的 children 为空，直接拿新节点的 text 和老节点的 text (不存在则为空)做比较，相等不动，不相等直接替换。

2、新节点的节点 children 不为空，老节点的 children 为空，直接用新节点替换老节点。

3、新节点的 children 和老节点的 children 皆不为空，执行 updateChildren()。

5、子节点的深度 diff

上面在新节点的 children 和老节点的 children 皆不为空的情况下，执行 updateChildren(elm, oldCh, ch, insertedVnodeQueue) 进行了深度比较，下面再来分析子节点的比较。

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

    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (oldStartVnode == null) {
       // 老节点开始位置为 null
        oldStartVnode = oldCh[++oldStartIdx];
      } else if (oldEndVnode == null) {
       // 老节点结束位置为 null
        oldEndVnode = oldCh[--oldEndIdx];
      } else if (newStartVnode == null) {
       // 新节点开始位置为 null
        newStartVnode = newCh[++newStartIdx];
      } else if (newEndVnode == null) {
        // 新节点结束位置为 null
        newEndVnode = newCh[--newEndIdx];
      } else if (sameVnode(oldStartVnode, newStartVnode)) {
       // 老节点开始位置与新节点开始位置 diff
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
        oldStartVnode = oldCh[++oldStartIdx];
        newStartVnode = newCh[++newStartIdx];
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
       // 老节点结束位置与新节点结束位置 diff
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
        oldEndVnode = oldCh[--oldEndIdx];
        newEndVnode = newCh[--newEndIdx];
      } else if (sameVnode(oldStartVnode, newEndVnode)) {
       // 老节点结束位置与新节点开始位置 diff
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
        api.insertBefore(
          parentElm,
          oldStartVnode.elm!,
          api.nextSibling(oldEndVnode.elm!)
        );
        oldStartVnode = oldCh[++oldStartIdx];
        newEndVnode = newCh[--newEndIdx];
      } else if (sameVnode(oldEndVnode, newStartVnode)) {
        // 老节点开始位置与新节点结束位置 diff
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
        api.insertBefore(parentElm, oldEndVnode.elm!, oldStartVnode.elm!);
        oldEndVnode = oldCh[--oldEndIdx];
        newStartVnode = newCh[++newStartIdx];
      } else {
        if (oldKeyToIdx === undefined) {
        // 将老节点转换成 map 结构
          oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
        }
        // 在 map 中找新节点的开始位置
        idxInOld = oldKeyToIdx[newStartVnode.key as string];
        if (isUndef(idxInOld)) {
          // 如果没找到，新节点开始位置是新元素
          api.insertBefore(
            parentElm,
            createElm(newStartVnode, insertedVnodeQueue),
            oldStartVnode.elm!
          );
        } else { // 如果找到了，则比较两个节点的选择器是否相等
          elmToMove = oldCh[idxInOld];
          if (elmToMove.sel !== newStartVnode.sel) {
          // 如果不相等，新节点开始位置是新元素
            api.insertBefore(
              parentElm,
              createElm(newStartVnode, insertedVnodeQueue),
              oldStartVnode.elm!
            );
          } else { // 如果相等，则认为是相同的元素
            patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
            oldCh[idxInOld] = undefined as any;
            api.insertBefore(parentElm, elmToMove.elm!, oldStartVnode.elm!);
          }
        }
        // 新节点开始位置右移
        newStartVnode = newCh[++newStartIdx];
      }
    }
    if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
    // 如果遍历完了
      if (oldStartIdx > oldEndIdx) {
      // 如果有残余的新节点未参与 diff，则全部 append 到父元素中
        before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].elm;
        addVnodes(
          parentElm,
          before,
          newCh,
          newStartIdx,
          newEndIdx,
          insertedVnodeQueue
        );
      } else {
      // 如果有残余的老节点未参与 diff，则全部移除
        removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
      }
    }
  }

子节点的 diff 应该算是整个整个 diff 过程当中最复杂的环节了，所以还是按照惯例，先上图：

结合代码和流程图来看：

1、首先是判断新老节点的开始和结束位置是否为 null；如果为 null，则将对应节点的位置左移（开始位置）或者右移（结束位置）。

2、然后依次拿新节点的开始位置与老节点的开始位置、新节点的结束位置与老节点的结束位置、新节点的结束位置与老节点的开始位置和新节点的开始位置与老节点的结束位置做对比，对比的逻辑依然是前面提到的 sameVnode 函数。如果匹配到，则再次进入 patchVnode 中，并且，对应的位置分别左移（开始位置）或右移（结束位置）；如果匹配不到，则在所有老的子节点中寻找新节点开始位置的 vnode。

3、当循环条件 oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx 不满足时，检查新子节点中是否有残余的子节点未参与 diff 过程，如果有，则插入所有残余新子节点；检查老的子节点，是否有残余的子节点未参与 diff 过程，如果有，则删除所有残余老子节点。