Vue 虚拟 DOM 与 diff 算法原理（手写 snabbdom）

snabbdom 虚拟 DOM 库

Vue 源码借鉴了 snabbdom, git 地址

虚拟 DOM 真实 DOM

虚拟 DOM

虚拟 DOM：用 JavaScript 对象描述 DOM 的层次结构。DOM 中的一切属性都在虚拟 DOM 中有对应的属性。

diff 是发生在虚拟 DOM 上的

新虚拟 DOM 和老虚拟 DOM 进行 diff（精细化比较），算出应该如何最小量更新，最后反映到真正的 DOM 上。

h 函数

h 函数用来产生虚拟节点（vnode）

// 比如这样调用h函数：
h('a', { props: { href: 'https://wflynn.cn/mio-blog/blog/' }}, 'mio');
// 将得到这样的虚拟节点：
{ "sel": "a", "data": { props: { href: 'https://wflynn.cn/mio-blog/blog/' } }, "text": "mio" }
// 它表示的真正的DOM节点：
&lt;a href="http://www.atguigu.com">尚硅谷&lt;/a>

虚拟节点有哪些属性

{
  children: undefined
  data: {}
  elm: undefined
  key: undefined
  sel: "div"
  text: "我是一个盒子"
}

简易版 h 函数

import vnode from './vnode.js';

// 编写一个低配版本的h函数，这个函数必须接受3个参数，缺一不可
// 相当于它的重载功能较弱。
// 也就是说，调用的时候形态必须是下面的三种之一：
// 形态① h('div', {}, '文字')
// 形态② h('div', {}, [])
// 形态③ h('div', {}, h())
export default function (sel, data, c) {
  // 检查参数的个数
  if (arguments.length !== 3)
    throw new Error('对不起，h函数必须传入3个参数，我们是低配版h函数');
  // 检查参数c的类型
  if (typeof c == 'string' || typeof c == 'number') {
    // 说明现在调用 h 函数是形态①
    return vnode(sel, data, undefined, c, undefined);
  } else if (Array.isArray(c)) {
    // 说明现在调用 h 函数是形态②
    let children = [];
    // 遍历c，收集children
    for (let i = 0; i < c.length; i++) {
      // 检查 c[i] 必须是一个对象，如果不满足
      if (!(typeof c[i] == 'object' && c[i].hasOwnProperty('sel')))
        throw new Error('传入的数组参数中有项不是h函数');
      // 这里不用执行c[i]，因为你的测试语句中已经有了执行
      // 此时只需要收集好就可以了
      children.push(c[i]);
    }
    // 循环结束了，就说明 children 收集完毕了，此时可以返回虚拟节点了，它有 children 属性的
    return vnode(sel, data, children, undefined, undefined);
  } else if (typeof c == 'object' && c.hasOwnProperty('sel')) {
    // 说明现在调用h函数是形态③
    // 即，传入的c是唯一的children。不用执行c，因为测试语句中已经执行了c。
    let children = [c];
    return vnode(sel, data, children, undefined, undefined);
  } else {
    throw new Error('传入的第三个参数类型不对');
  }
}

vnode.js

// 函数的功能非常简单，就是把传入的5个参数组合成对象返回
export default function (sel, data, children, text, elm) {
  const key = data.key;
  return {
    sel,
    data,
    children,
    text,
    elm,
    key,
  };
}

使用示例

import { init } from 'snabbdom/init';
import { classModule } from 'snabbdom/modules/class';
import { propsModule } from 'snabbdom/modules/props';
import { styleModule } from 'snabbdom/modules/style';
import { eventListenersModule } from 'snabbdom/modules/eventlisteners';
import h from './mysnabbdom/h';

// 创建出patch函数
const patch = init([
  classModule,
  propsModule,
  styleModule,
  eventListenersModule,
]);

// 形态①
const myVnode1 = h(
  'a',
  {
    props: {
      href: 'http://www.atguigu.com',
      target: '_blank',
    },
  },
  '尚硅谷',
);
console.log('形态①:', myVnode1);

// 形态②
const myVnode2 = h('ul', {}, [h('li', {}, '苹果'), h('li', {}, '西瓜')]);
console.log('形态②:', myVnode2);

// 形态③
const myVnode3 = h('div', {}, h('span', {}, '西瓜'));
console.log('形态③:', myVnode3);

// 形态综合
const myVnode4 = h('ul', {}, [
  h('li', {}, '西瓜'),
  h('li', {}, h('span', {}, '苹果')),
  h('li', {}, [h('p', {}, '苹果'), h('em', {}, '西瓜')]),
]);
console.log('形态综合:', myVnode4);

// 让虚拟节点上树
const container = document.getElementById('container');
patch(container, myVnode3);

结果如下图

diff 算法

精细化比对最小量更新
diff 中的 key 很重要。key 是这个节点的唯一标识，告诉 diff 算法，在更改前后它们是同一个 DOM 节点。
只有是同一个虚拟节点，才进行精细化比较，否则就是暴力删除旧的、插入新的。
延伸问题：如何定义是同一个虚拟节点？答：选择器相同且 key 相同。

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

只进行同层比较，不会进行跨层比较。即使是同一片虚拟节点，但是跨层了，对不起，精细化比较不 diff 你，而是暴力删除旧的、然后插入新的。

如何提现 key 值的重要性

如下代码将 vNode1 更改为 vNode2 or vNode1 更改为 vNode3

如代码所示 vNode1 与 vNode2 中的数据 sel 与 key 值都保持一致，只是顺序改变了，vNode3 中没有 key 值
为了演示出效果可以在浏览器上对节点的 html 直接做更改。如图所示
可以发现 vNode2 改 vNode1，节点的文字没有改变，依旧是以前的节点，vNode3 改 vNode1，节点被更换了

import { init } from 'snabbdom/init';
import { classModule } from 'snabbdom/modules/class';
import { propsModule } from 'snabbdom/modules/props';
import { styleModule } from 'snabbdom/modules/style';
import { eventListenersModule } from 'snabbdom/modules/eventlisteners';
import { h } from 'snabbdom/h';

// 得到盒子和按钮
const container = document.getElementById('container');
const btn = document.getElementById('btn');

// 创建出patch函数
const patch = init([
  classModule,
  propsModule,
  styleModule,
  eventListenersModule,
]);

const vnode1 = h('ul', {}, [
  h('li', { key: 'A' }, 'A'),
  h('li', { key: 'B' }, 'B'),
  h('li', { key: 'C' }, 'C'),
  h('li', { key: 'D' }, 'D'),
]);

patch(container, vnode1);

const vnode2 = h('ul', {}, [
  h('li', { key: 'D' }, 'D'),
  h('li', { key: 'A' }, 'A'),
  h('li', { key: 'C' }, 'C'),
  h('li', { key: 'B' }, 'B'),
]);

const vnode3 = h('ul', {}, [
  h('li', 'D'),
  h('li', 'A'),
  h('li', 'C'),
  h('li', 'B'),
]);

// 点击按钮时，将vnode1变为vnode2
btn.onclick = function () {
  // patch(vnode1, vnode2);
  patch(vnode1, vnode3);
};

有 key 值
无 key 值

diff 处理新旧节点不是同一个节点时

patch.js 函数编写

import vnode from './vnode.js';
import createElement from './createElement.js';
import patchVnode from './patchVnode.js';

export default function patch(oldVnode, newVnode) {
  // 判断传入的第一个参数，是 DOM 节点还是虚拟节点？
  if (oldVnode.sel === '' || oldVnode.sel === undefined) {
    // 传入的第一个参数是 DOM 节点，此时要包装为虚拟节点
    oldVnode = vnode(
      oldVnode.tagName.toLowerCase(),
      {},
      [],
      undefined,
      oldVnode,
    );
  }

  // 判断 oldVnode 和 newVnode 是不是同一个节点
  if (oldVnode.key === newVnode.key && oldVnode.sel === newVnode.sel) {
    console.log('是同一个节点');
    patchVnode(oldVnode, newVnode);
  } else {
    console.log('不是同一个节点，暴力插入新的，删除旧的');
    let newVnodeElm = createElement(newVnode);
    // 插入到节点之前
    if (oldVnode.elm.parentNode && newVnodeElm) {
      oldVnode.elm.parentNode.insertBefore(newVnodeElm, oldVnode.elm);
    }
    // 删除老节点
    oldVnode.elm.parentNode.removeChild(oldVnode.elm);
  }
}

递归创建子节点 createElement.js 编写

// 真正创建节点。将vnode创建为DOM，是孤儿节点，不进行插入
export default function createElement(vnode) {
  // console.log('目的是把虚拟节点', vnode, '真正变为DOM');
  // 创建一个DOM节点，这个节点现在还是孤儿节点
  let domNode = document.createElement(vnode.sel);
  // 有子节点还是有文本？？
  if (
    vnode.text !== '' &&
    (vnode.children === undefined || vnode.children.length === 0)
  ) {
    // 它内部是文字
    domNode.innerText = vnode.text;
  } else if (Array.isArray(vnode.children) && vnode.children.length > 0) {
    // 它内部是子节点，就要递归创建节点
    for (let i = 0; i < vnode.children.length; i++) {
      // 得到当前这个children
      let ch = vnode.children[i];
      // 创建出它的DOM，一旦调用createElement意味着：创建出DOM了，并且它的elm属性指向了创建出的DOM，但是还没有上树，是一个孤儿节点。
      let chDOM = createElement(ch);
      // 上树
      domNode.appendChild(chDOM);
    }
  }
  // 补充elm属性
  vnode.elm = domNode;

  // 返回elm，elm属性是一个纯DOM对象
  return vnode.elm;
}

diff 处理新旧节点是同一个节点时

编写 patchVnode.js 函数。对比同一个虚拟节点时使用

import createElement from './createElement';
import updateChildren from './updateChildren.js';

// 对比同一个虚拟节点
export default function patchVnode(oldVnode, newVnode) {
  // 判断新旧vnode是否是同一个对象
  if (oldVnode === newVnode) return;
  // 判断新vnode有没有text属性
  if (
    newVnode.text !== undefined &&
    (newVnode.children === undefined || newVnode.children.length === 0)
  ) {
    // 新vnode有text属性
    console.log('新vnode有text属性');
    if (newVnode.text !== oldVnode.text) {
      // 如果新虚拟节点中的text和老的虚拟节点的text不同，那么直接让新的text写入老的elm中即可。如果老的elm中是children，那么也会立即消失掉。
      oldVnode.elm.innerText = newVnode.text;
    }
  } else {
    // 新vnode没有text属性，有children
    console.log('新vnode没有text属性');
    // 判断老的有没有children
    if (oldVnode.children !== undefined && oldVnode.children.length > 0) {
      // 老的有children，新的也有children，此时就是最复杂的情况。
      updateChildren(oldVnode.elm, oldVnode.children, newVnode.children);
    } else {
      // 老的没有children，新的有children
      // 清空老的节点的内容
      oldVnode.elm.innerHTML = '';
      // 遍历新的vnode的子节点，创建DOM，上树
      for (let i = 0; i < newVnode.children.length; i++) {
        let dom = createElement(newVnode.children[i]);
        oldVnode.elm.appendChild(dom);
      }
    }
  }
}

old/newVnode 都有 children

diff 算法优化策略四种命中查找：
- ① 新前与旧前
- ② 新后与旧后
- ③ 新后与旧前（此种发生了，涉及移动节点，那么新前指向的节点，移动的旧后之后）
- ④ 新前与旧后（此种发生了，涉及移动节点，那么新前指向的节点，移动的旧前之前）
- 命中一种就不再进行命中判断了
- 如果都没有命中，就需要用循环来寻找了。移动到 oldStartIdx 之前。
如果是旧节点先循环完毕，说明新节点中有要插入的节点。
如果是新节点先循环完毕，如果老节点中还有剩余节点，说明他们是要被删除的节点。
当 ④ 新前与旧后命中的时候，此时要移动节点。移动新前指向的这个节点到老节点的旧前的前面
当 ③ 新后与旧前命中的时候，此时要移动节点。移动新前指向的这个节点到老节点的旧后的后面
updateChildren.js 编写

import patchVnode from './patchVnode.js';
import createElement from './createElement.js';

// 判断是否是同一个虚拟节点
function checkSameVnode(a, b) {
  return a.sel === b.sel && a.key === b.key;
}

export default function updateChildren(parentElm, oldCh, newCh) {
  console.log('我是updateChildren');
  console.log(oldCh, newCh);

  // 旧前
  let oldStartIdx = 0;
  // 新前
  let newStartIdx = 0;
  // 旧后
  let oldEndIdx = oldCh.length - 1;
  // 新后
  let newEndIdx = newCh.length - 1;
  // 旧前节点
  let oldStartVnode = oldCh[0];
  // 旧后节点
  let oldEndVnode = oldCh[oldEndIdx];
  // 新前节点
  let newStartVnode = newCh[0];
  // 新后节点
  let newEndVnode = newCh[newEndIdx];

  let keyMap = null;

  // 开始大while了
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    console.log('★');
    // 首先不是判断①②③④命中，而是要略过已经加undefined标记的东西
    if (oldStartVnode == null || oldCh[oldStartIdx] === undefined) {
      oldStartVnode = oldCh[++oldStartIdx];
    } else if (oldEndVnode == null || oldCh[oldEndIdx] === undefined) {
      oldEndVnode = oldCh[--oldEndIdx];
    } else if (newStartVnode == null || newCh[newStartIdx] === undefined) {
      newStartVnode = newCh[++newStartIdx];
    } else if (newEndVnode == null || newCh[newEndIdx] === undefined) {
      newEndVnode = newCh[--newEndIdx];
    } else if (checkSameVnode(oldStartVnode, newStartVnode)) {
      // 新前和旧前
      console.log('①新前和旧前命中');
      patchVnode(oldStartVnode, newStartVnode);
      oldStartVnode = oldCh[++oldStartIdx];
      newStartVnode = newCh[++newStartIdx];
    } else if (checkSameVnode(oldEndVnode, newEndVnode)) {
      // 新后和旧后
      console.log('②新后和旧后命中', oldEndVnode, newEndVnode);
      patchVnode(oldEndVnode, newEndVnode);
      oldEndVnode = oldCh[--oldEndIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (checkSameVnode(oldStartVnode, newEndVnode)) {
      // 新后和旧前
      console.log('③新后和旧前命中');
      patchVnode(oldStartVnode, newEndVnode);
      // 当③新后与旧前命中的时候，此时要移动节点。移动新前指向的这个节点到老节点的旧后的后面
      // 如何移动节点？？只要你插入一个已经在DOM树上的节点，它就会被移动
      parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling);
      oldStartVnode = oldCh[++oldStartIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (checkSameVnode(oldEndVnode, newStartVnode)) {
      // 新前和旧后
      console.log('④新前和旧后命中');
      patchVnode(oldEndVnode, newStartVnode);
      // 当④新前和旧后命中的时候，此时要移动节点。移动新前指向的这个节点到老节点的旧前的前面
      parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm);
      // 如何移动节点？？只要你插入一个已经在DOM树上的节点，它就会被移动
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
    } else {
      // 四种命中都没有命中
      // 制作keyMap一个映射对象，这样就不用每次都遍历老对象了。
      if (!keyMap) {
        keyMap = {};
        // 从oldStartIdx开始，到oldEndIdx结束，创建keyMap映射对象
        for (let i = oldStartIdx; i <= oldEndIdx; i++) {
          const key = oldCh[i].key;
          if (key !== undefined) {
            keyMap[key] = i;
          }
        }
      }
      console.log(keyMap);
      // 寻找当前这项（newStartIdx）这项在keyMap中的映射的位置序号
      const idxInOld = keyMap[newStartVnode.key];
      console.log(idxInOld);
      if (idxInOld === undefined) {
        // 判断，如果idxInOld是undefined表示它是全新的项
        // 被加入的项（就是newStartVnode这项)现不是真正的DOM节点
        parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm);
      } else {
        // 如果不是undefined，不是全新的项，而是要移动
        const elmToMove = oldCh[idxInOld];
        patchVnode(elmToMove, newStartVnode);
        // 把这项设置为undefined，表示我已经处理完这项了
        oldCh[idxInOld] = undefined;
        // 移动，调用insertBefore也可以实现移动。
        parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm);
      }
      // 指针下移，只移动新的头
      newStartVnode = newCh[++newStartIdx];
    }
  }

  // 继续看看有没有剩余的。循环结束了start还是比old小
  if (newStartIdx <= newEndIdx) {
    console.log(
      'new还有剩余节点没有处理，要加项。要把所有剩余的节点，都要插入到oldStartIdx之前',
    );
    // 遍历新的newCh，添加到老的没有处理的之前
    for (let i = newStartIdx; i <= newEndIdx; i++) {
      // insertBefore方法可以自动识别null，如果是null就会自动排到队尾去。和appendChild是一致了。
      // newCh[i]现在还没有真正的DOM，所以要调用createElement()函数变为DOM
      parentElm.insertBefore(createElement(newCh[i]), oldCh[oldStartIdx].elm);
    }
  } else if (oldStartIdx <= oldEndIdx) {
    console.log('old还有剩余节点没有处理，要删除项');
    // 批量删除oldStart和oldEnd指针之间的项
    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
      if (oldCh[i]) {
        parentElm.removeChild(oldCh[i].elm);
      }
    }
  }
}