vue中的VDOM和diff算法-一一网

为啥会有VDOM？

真实DOM是怎么工作的

真实DOM的渲染大致分为5步，创建DOM树——创建StyleRules——创建Render树——布局——绘制。

用HTML分析器，分析HTML元素，构建一颗DOM树(标记化和树构建)。
用CSS分析器，分析CSS文件和元素上的inline样式，生成页面的样式表。
第三步，将DOM树和样式表，关联起来，构建一颗Render树(这一过程又称为Attachment)。每个DOM节点都有attach方法，接受样式信息，返回一个render对象(又名renderer)。这些render对象最终会被构建成一颗Render树。
第四步，有了Render树，浏览器开始布局，为每个Render树上的节点确定一个在显示屏上出现的精确坐标。
第五步，Render树和节点显示坐标都有了，就调用每个节点paint方法，把它们绘制出来。

真实DOM的更新

我们用jQuery操作DOM时，浏览器会从构建DOM树开始从头到尾执行一遍流程。在一次操作中，我需要更新10个DOM节点，浏览器收到第一个DOM请求后并不知道还有9次更新操作，因此会马上执行流程，最终执行10次。例如，第一次计算完，紧接着下一个DOM更新请求，这个节点的坐标值就变了，前一次计算为无用功。计算DOM节点坐标值等都是白白浪费的性能。即使计算机硬件一直在迭代更新，操作DOM的代价仍旧是昂贵的，频繁操作还是会出现页面卡顿，影响用户体验。

于是乎，VDOM就应运而生了。用JS去模拟DOM结构，计算出最小的变更，然后再操作DOM。

用VNode模拟DOM结构

<div id='div1' class='container'>
    <p>vdom</p>
    <ul style='font-size: 20px;'>
        <li>a</li>
    </ul>
</div>
复制代码

VNode模拟

{
    tag: 'div',
    props: {
        id: 'div1',
        className: 'container',
    },
    children: [
        {
            tag: 'p',
            children: 'vdom',
        },
        {
            tag: 'ul',
            props: {
                style: 'font-size: 20px'
            },
            children: [
                {
                    tag: 'li',
                    children: 'a'
                },
            ]
        }
    ]
}
复制代码

diff算法

用VDOM来模拟DOM之后，我们可以用diff算法计算出Virtual DOM中真正变化的部分，并只针对该部分进行原生DOM操作，而非重新渲染整个页面。

传统diff算法

diff算法是一个广泛的概念，比如linux diff命令，git diff等。两个js对象也可以做diff。还有两棵树做diff，比如这里的vdom diff。

我们拿树的diff算法来说，通过对两棵树循环递归对每个节点进行对比，算法的复杂度就达到了O(n^3),n是数的节点数。所以，如果我们要展示1000个节点，我们就需要执行1亿次比较。。。这个就比较恐怖了。。。

优化后的diff算法

优化后的diff算法将O(n^3)复杂度转化为O(n),通过下面几个策略：

只比较同一层级，不跨级比较

tag不相同，则直接删掉重建，不再深度比较

Screen Shot 2021-06-16 at 3.22.58 PM.png

tag和key，两者都相同，则认为是相同节点，不再深度比较。

VNode 和 diff算法相结合

vue在官方文档中提到与react的渲染性能对比中，因为其使用了snabbdom而有更优异的性能。

JavaScript 开销直接与求算必要 DOM 操作的机制相关。尽管 Vue 和 React 都使用了 Virtual Dom 实现这一点，但 Vue 的 Virtual Dom 实现（复刻自 snabbdom）是更加轻量化的，因此也就比 React 的实现更高效。

下面咱们就通过snabbdom源码来看看吧～

VNode

在文章一开始，我们就用VNode来模拟DOM，那什么是VNode呢？

Snabbdom 的 Virtual Node 则是纯数据对象，通过 vnode 模块来创建，对象属性包括：

sel
data
children
text
elm
key

可以看到 Virtual Node 用于创建真实节点的数据包括：

元素类型
元素属性
元素的子节点

//VNode函数，用于将输入转化成VNode
    /**
     *
     * @param sel    选择器
     * @param data    绑定的数据
     * @param children    子节点数组
     * @param text    当前text节点内容
     * @param elm    对真实dom element的引用
     * @returns {{sel: *, data: *, children: *, text: *, elm: *, key: undefined}}
     */
function vnode(sel, data, children, text, elm) {
     var key = data === undefined ? undefined : data.key;
      return { sel: sel, data: data, children: children,
          text: text, elm: elm, key: key };
}
复制代码

但是呢，Snabbdom并没有把vnode直接暴露给我们用，而是用了h包装起，h的主要功能是处理参数：

h(sel,[data],[children],[text]) => vnode
复制代码

从Snabbdom的源码可以看出，其实就是这几种函数：

export function h(sel: string): VNode; 
export function h(sel: string, data: VNodeData): VNode; 
export function h(sel: string, text: string): VNode; 
export function h(sel: string, children: Array<VNode | undefined | null>): VNode; 
export function h(sel: string, data: VNodeData, text: string): VNode; 
export function h(sel: string, data: VNodeData, children: Array<VNode | undefined | null>): VNode; 
复制代码

patch

创建vnode之后，接下来就是调用patch()渲染成真实dom。

patch是snabbdom的init函数返回的。snabbdom.init传入modules数组，module用来扩展snabbdom创建复杂dom的能力。

上patch源码

return function patch(oldVnode: VNode | Element, vnode: VNode): VNode {
    let i: number, elm: Node, parent: Node;
    const insertedVnodeQueue: VNodeQueue = [];
    
    //执行callback pre hook（dom的生命周期）
    for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]();

    //第一个参数不是vnode
    if (!isVnode(oldVnode)) {
      //创建一个空的vnode，关联到这个DOM元素
      oldVnode = emptyNodeAt(oldVnode);
    }

    //相同的vnode（key 和 sel 都相同）
    if (sameVnode(oldVnode, vnode)) {
      patchVnode(oldVnode, vnode, insertedVnodeQueue);
    } 
    //不同的vnode，直接删除重建
    else { 
      elm = oldVnode.elm!;
      parent = api.parentNode(elm) as Node;

      //重建
      createElm(vnode, insertedVnodeQueue);

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

    for (i = 0; i < insertedVnodeQueue.length; ++i) {
      insertedVnodeQueue[i].data!.hook!.insert!(insertedVnodeQueue[i]);
    }
    for (i = 0; i < cbs.post.length; ++i) cbs.post[i]();
    return vnode;
  };
复制代码

先判断oldVnode和vnode是否是相同的，如果是才可以执行patchVnode，否则创建新的dom删除旧的dom。
判断是否相同的源码很简单，根据优化后的diff算法策略1和3，只在同一级比较key和tag：

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;
}
复制代码

如果相同，则调用patchVnode进行对比。