vue源码——vDOM与Diff算法

前言

入职第一个月开发公司一个小项目，由于项目比较小，因此由我一人担任前后端。在前端开发时，使用到了Element-UI的table组件。由于项目需要，需要对table组件进行样式的自定义设置。当时遇到了一个解决了很久的bug，当时还是求助公司的大牛才顺利解决。贴上当时的Bug记录：

【环境】

vue2.0+elementUI

【背景】

左右布局，左边是element table，右边是自己设计的菜单。左边table里装着全部分类的数据，右边菜单是每个分类的类别。

【需求】

点击右边菜单的类别，右侧样式跟随点击处，左边表格数据会自动选择对应数据并跟随。

【问题】

点击右边菜单，样式正常跟随，左侧表格却需要点击两次。排查后发现，只要修改控制样式的变量就会出现左侧表格的重新渲染。不修改控制样式的变量，一切正常。

【解析】

element table 有一个key控制渲染，因为我这里已经设置了随机值，所以只要页面上有变量更改，table就会刷新。

【解决】

element table key设置为固定值。

后来试用期的导师解释道：“由于vue的diff算法原因，因此修改变量会导致table的重新渲染，可以去了解一下diff算法”。

因此，有了这篇笔记。

概念

虚拟DOM

虚拟DOM（Virtual DOM），用普通js对象来描述DOM结构，因为不是真实DOM，所以称之为虚拟DOM。

虚拟DOM是相对于浏览器所渲染出来的真实的DOM而言的。在react、vue等技术出现之前，我们要改变页面展示的内容，只能通过遍历查询DOM树的方式找到需要修改的DOM，然后修改样式行为或者结构，以此来达到更新UI的目的。

但这种方式相当消耗计算资源，因为每次查询 DOM 几乎都需要遍历整棵 DOM 树，如果建立一个与 DOM 树对应的虚拟 DOM 对象（ js 对象），以对象嵌套的方式来表示 DOM 树及其层级结构，那么每次 DOM 的更改就变成了对 js 对象的属性的增删改查，这样一来查找 js 对象的属性变化要比查询 DOM 树的性能开销小。

作用

• 可以维护视图和状态之间的关系
• 复杂视图情况下提升渲染性能
• 虚拟DOM除了可以渲染成DOM节点，还可以渲染到其他平台如ssr(nuxt.js/next.js)、原生应用（weex/rn）、小程序等，增加了跨平台能力

开源库

• snabbdom

  • vue 2.x就是使用的snabbdom并进行了一定的改造
  • 代码量少
  • 可以通过模块进行扩展
  • 源码使用ts开发

• virtual-dom

问题

1.真实DOM解析流程是什么？

浏览器渲染引擎工作流程都差不多，大致分为5步：创建DOM树——创建StyleRules——创建Render树——布局Layout——绘制Painting。

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

注意：

• DOM树的构建是文档加载完成开始的？

  • 构建DOM数是一个渐进过程，为达到更好用户体验，渲染引擎会尽快将内容显示在屏幕上。它不必等到整个HTML文档解析完毕之后才开始构建render数和布局。

• Render树是DOM树和CSSOM树构建完毕才开始构建的吗？

  • 这三个过程在实际进行的时候又不是完全独立，而是会有交叉。会造成一边加载，一遍解析，一遍渲染的工作现象。

• CSS的解析是从右往左逆向解析的(从DOM树的下－上解析比上－下解析效率高)，嵌套标签越多，解析越慢。

  图：webkit渲染引擎工作流程

2.为什么操作真实的DOM会比操作虚拟的DOM成本更高？

• DOM 树的实现模块和 js 模块是分开的这些跨模块的通讯增加了成本；
• DOM 操作引起的浏览器的回流和重绘，使得性能开销巨大。

原本在 pc 端是没有性能问题的，因为pc端的计算能力强，但是随着移动端的发展，越来越多的网页在智能手机上运行，而手机的性能参差不齐，会有性能问题。用jquery在pc端写那些商城页面没有问题，但放到移动端浏览器访问之后可能会发现除了首页会出现白屏之外在其他页面的操作并不流畅。

但需要注意，虚拟DOM的性能不一定绝对高于真实DOM。

原因是因为，使用Diff算法是为了有的放矢地去更新页面，但需要注意，比较过程也是消耗性能的。对于简单的页面操作，直接操作DOM的过程就是一个有的放矢的过程，因为我们知道该更新什么，不该更新什么，所以不需要有比较的过程。

此外，使用了虚拟DOM并非不操作DOM元素。虚拟DOM只是减少了用户操作DOM，虚拟DOM在渲染的时候，还是会操作DOM的。

3.什么是回流和重绘？

• 回流（Reflow）：当呈现树renderTree中的一部分或全部因为尺寸、布局、隐藏等改变改重新构建，称之为回流。
• 重绘（Redraw）：当呈现树renderTree中的一部分元素需要更新属性，而属性只会影响外观、风格而不影响布局，比如颜色、字体大小等，则称之为重绘。

实现虚拟DOM

真实DOM：

xxxxxxxxxx
9
1
<div id="real-container">
2
    <p>ReaL DOM</p>
3
    <div>cannot update</div>
4
    <ul>
5
        <li className="item">Item 1</li>
6
        <1i className="item">Item 2</1i>
7
        <li className="item">Item 3</li>
8
    </ul>
9
</div>

使用JS模拟的虚拟DOM：

xxxxxxxxxx
12
1
const tree = Element(' div', {id: ' virtual-container'}, I
2
Element('p', {}, [' Virtual DOM']),
3
    Element('div', {}, [' before update']),
4
    Element('ul', {}, [
5
      Element('li', {class: 'item'}, [' Item 1']),
6
      Element('li', {class: 'item'}, [' Item 2']),
7
      Element('li', {class: 'item'}, [' Item 3']),
8
    ]),
9
]);
10

11
const root = tree.render();
12
document.getElementById('virtualDom').appendChild(root);

其中Element方法实现原理如下：

xxxxxxxxxx
19
1
function Element(tagName, props, children) {
2
  if (!(this instanceof Element)) {
3
    return new ELement(tagName, props, children);
4
  }
5

6
  this.tagName = tagName;
7
  this.props = props || {};
8
  this.children = children || [];
9
  this.key = props ? props.key : undefined;
10

11
  let count = 0;
12
  this.children.forEach((child) => {
13
    if (child instanceof Element) {
14
      count += child.count;
15
    }
16
    count++;
17
  });
18
  this.count = count;
19
}

第一个参数是节点名（如div），第二个参数是节点的属性（如class），第三个参数是子节点（如ul的li）。除了这三个参数会被保存在对象上外，还保存了key和count。其相当于形成了虚拟DOM树。

有了JS对象后，最终还需要将其映射成真实DOM。

xxxxxxxxxx
15
1
CreateElement.prototype.render = function() {
2
    let el = document.createElement(this.tagName);
3
    let props = this.props;
4

5
    for (let propName in props) {
6
        setAttr(el, propName, props[propName]);
7
    }
8

9
    this.children.forEach((child) => {
10
        let childEl = (child instanceof Element) ? child.render() : document.createTextNode(child);
11
        el.appendChild(childEl);
12
    });
13

14
    return el;
15
};

Diff算法原理

算法原理

比较两棵Dom树的差异，虚拟Dom算法最核心的部分，这也就是Diff算法。

Diff的原理就是当前的真实的DOM生成一棵Virtual DOM也就是虚拟DOM，当虚拟DOM的某个节点的数据发生改变会生成一个新的Vnode, 然后这个Vnode和旧的oldVnode对比，发现有不同，直接修改在真实DOM上。

其中需要注意的是，要比较两棵树完全相同的时间复杂度是O(n^3)（具体原因见该论文），而React的Diff算法的时间复杂度是O(n)。要实现如此低的时间复杂度，意味着只能平层进行比较两棵树的节点，从而放弃深度遍历。纵然这样做会牺牲掉一定程度上的精确性来换取速度，但考虑到现实情况中，前端页面通常也不会跨层移动DOM元素。也就是，同一个层级的元素只会和同一个层级的进行比较，第一层的div只会和同一层级的div对比，第二层级的只会和第二层级的对比。这样算法复杂度就可以达到O(n)，因此这样做是最优的。

Diff操作

在实际代码中，会对新旧两棵树进行一个深度的遍历，每个节点都会有一个标记。每遍历到一个节点就把该节点和新的树进行对比，如果有差异就记录到一个对象中。

下面我们创建一棵新树，用于和之前的树进行比较，来看看Diff算法是怎么操作的。

xxxxxxxxxx
28
1
/*
2
* Old tree
3
*/
4
const tree = Element('div', {id: 'virtual-container'}, 
5
    Element('p', {}, ['Virtual DOM']),
6
    Element('div', {}, ['before update']),
7
    Element('ul', {}, [
8
      Element('li', {class: 'item'}, [' Item 1']),
9
      Element('li', {class: 'item'}, [' Item 2']),
10
      Element('li', {class: 'item'}, [' Item 3']),
11
    ]),
12
]);
13
 
14
const root = tree.render();
15
document.getElementById('virtualDom').appendChild(root);
16

17
/*
18
* New tree
19
*/
20
const tree = Element('div', {id: 'virtual-container'}, 
21
    Element('h3', {}, ['Virtual DOM']),                // REPLACE
22
    Element('div', {}, ['after update']),              // TEXT
23
    Element('ul', {class: 'marginLeft10'}, [           // PROPS
24
      Element('li', {class: 'item'}, ['Item 1']),
25
      // Element('li', {class: 'item'}, ['Item 2']),   // REORDER remove
26
      Element('li', {class: 'item'}, ['Item 3']),
27
    ]),
28
]);

由于是平层比较的Diff算法，因此只有下列4种情况：

1. 节点类型变化

   例如上面的p标签变成了h3标签，这个过程称之为REPLACE，直接卸载旧节点、装载新节点，旧节点包括下面的子节点都将被卸载。

   但当遇到新节点和旧节点仅仅是类型不同，但下面的所有的子节点都一样时，这样做的效率明显不高。尽管如此，与整个树的操作相比，这样还是值得的。

   同时也能提醒开发者，在编程的时候应当避免无谓的节点类型，例如运行时将div变成p没有意义。

2. 节点类型一致，但属性或属性值改变

   例如上面的ul标签增加了类属性'marginLeft10'。这个过程称之为PROPS。此时不会触发节点的卸载和装载，只是节点更新。

   xxxxxxxxxx
   26
   1
   // 查找不同属性的方法
   2
   function diffProps(oldNode, newNode) {
   3
     const oldProps = oldNode.props;
   4
     const newProps = newNode.props;
   5
   
   6
     let key;
   7
     const propsPatches = {};
   8
     let isSame = true;
   9
   
   10
     // find out different props
   11
     for (key in oldProps) {
   12
       if (newProps[key] !== oldProps[key]) {
   13
         isSame = false;
   14
         propsPatches[key] = newProps[key];
   15
       }
   16
     }
   17
   
   18
     // find out new props
   19
     for (key in newProps) {
   20
       if (!oldProps.hasOwnProperty(key)) {
   21
         isSame = false;
   22
         propsPatches[key] = newProps[key];
   23
       }
   24
     }
   25
     return isSame ? null : propsPatches;
   26
   }
   

3. 文本内容改变

   文本对也是一个Text Node，直接修改文字内容即可。这个过程称之为TEXT。

4. 移动 / 增加 / 删除 子节点

   这个过程称之为REODER。如下图，在A、B、C、D、E五个节点的B和C中的BC两个节点中间加入一个F节点。

   

   简单粗暴的做法是遍历每一个新虚拟DOM的节点，与旧虚拟DOM对比相应节点对比，在旧DOM中是否存在，不同就卸载原来的按上新的。这样会对F后边每一个节点进行操作。卸载C，装载F，卸载D，装载C，卸载E，装载D，装载E。效率太低。

   

   如果我们在React里的JSX里，为数组或枚举型元素增加上key后，它能够根据key。当要对某个节点进行操作时，就可以直接找到具体位置进行操作，效率比较高。常见的最小编辑距离问题，可以用Levenshtein Distance算法来实现，时间复杂度是O(M*N)，但通常前端只要一些简单的移动就能满足需要，降低精确性，将时间复杂度降低到O(max(M,N))即可。最终Diff出来的结果如下：

   xxxxxxxxxx
   6
   1
   {
   2
       1: [{type: REPLACE, node: Element}],
   3
       2: [{type: TEXT, content: "after update"}],
   4
       3: [{type: PROPS, props: {class: "marginLeft10"}}],
   5
       4: [{type: REORDER, moves: {index: 2, type: 0}}],
   6
   }
   

    

映射成真实DOM

根据上述操作，此时我们已经有了虚拟的DOM，也有了Diff的结果，因此就可以将结果应用到真实的DOM上了。深度遍历DOM将Diff的内容更新进去。

具体的代码如下：

xxxxxxxxxx
43
1
function dfsWalk(node, walker, patches) {
2
  const currentPatches = patches[walker.index];
3
  
4
  const len = node.childNodes ? node.childNodes.length : 0;
5
  for (leti = 0; i < len; i++) {
6
    walker.index++;
7
    dfsWalk(node.childNodes[il, walker, patches);
8
  }
9
  
10
  if (currentPatches) {
11
    applyPatches(node, currentPatches);
12
  }
13
}
14

15
function applyPatches(node, currentPatches) {
16
  currentPatches.forEach((currentPatch) => {
17
    switch (currentPatch.type) {
18
      case REPLACE: {
19
        const neNode = (typeof currentPatch.node === 'string')
20
            ? document.createTextNode(currentPatch.node)
21
            : currentPatch.node.render();
22
        node.parentNode.replaceChild(neNode, node);
23
        break;
24
      }
25
      case REORDER:
26
        reorderChildren(node, currentPatch.moves);
27
        break;
28
      case PROPS:
29
        setProps(node, currentPatch.props);
30
        break;
31
      case TEXT:
32
        if (node.textContent) {
33
          node.textContent = currentPatch.content;
34
        } else {
35
          //ie
36
          node.nodeValue = currentPatch.content;
37
        }
38
        break;
39
      default:
40
        throw new Error(`Unknown patch type ${currentPatch.type}`);
41
    }
42
  });
43
}

总结

简而言之，会使用两个虚拟的DOM（JS对象，new/old进行比较diff)，用户交互后，操作数据变化new虚拟DOM，而old虚拟DOM则会映射成真实DOM（js对象生成的DOM文档），通过js的DOM fragment 操作给浏览器渲染。当修改new虚拟DOM时，会把newDOM和oldDOM通过Diff算法比较，得出Diff结果数据表（用4种变换情况表示），最后再把Diff的结果表通过JS的DOM fragment更新到浏览器DOM中。

虚拟DOM的性能未必就会比真实DOM高。此外，即使使用了虚拟DOM，也依旧是需要操作DOM的。在Vue中，则是使用了JS的DOM fragment来操作DOM，这样在Diff算法计算出所有的变化后，一次性统一更新浏览器DOM。像Vue，React这类框架的价值是为了让程序员专注于业务代码，将对DOM的操作，全部放到DOM fragment里。

因此，纵然虚拟DOM虽好，但切勿贪杯。

参考文献

• 什么是虚拟DOM

• vue核心之虚拟DOM(vdom)

• 传统diff算法的时间复杂度为什么是O(n^3)?

• diff算法的时间复杂度

• 虚拟DOM为何出现以及性能问题