步骤1：用js对象模拟DOM树

用js来表示一个DOM节点是很简单的事情，你只需要记录它的节点类型、属性，还有子节点：
element.js

  1. function Element(tagName, props, children){
  2.     this.tagName = tagName;
  3.     this.props = props;
  4.     this.children = children;
  5. }
  6. module.exports = function(tagName, props, children){
  7.     return new Element(tagName, props, children);
  8. }

例如上面的DOM结构就可以简单的表示：

  1. var el = require('./element');
  2. var ul = el(
  3.     'ul', 
  4.     {id: 'list'}, 
  5.     [        el('li', {class: 'item'}, ['item 1']),
  6.         el('li', {class: 'item'}, ['item 2']),
  7.         el('li', {class: 'item'}, ['item 3']),
  8.     ])

现在ul只是一个js对象表示的DOM结构，页面上还没有这个结构，我们可以根据这个ul构建真正的ul：

  1. //渲染真正的DOM
  2. Element.prototype.render = function(){
  3.     var el = document.createElement(this.tagName);
  5.     var props = this.props || {};
  6.     for(let propName in props){
  7.         var propValue = props[propName];
  8.         el.setAttribute(propName, propValue);
  9.     }
  11.     var children = this.children || [];
  12.     children.forEach(function(child){
  13.         var childEl = (child instanceof Element) ? child.render() : document.createTextNode(child);
  14.         el.appendChild(childEl);
  15.     });
  17.     return el;
  18. }

render方法会根据tagName构建一个真正的DOM节点，然后设置这个节点的属性，最后递归的把自己的子节点构建起来，所以只需要：

  1. var ulRoot = ul.render();
  2. document.body.appendChild(ulRoot);

把ulRoot真正的DOM节点塞到文档中

步骤2：比较两颗虚拟DOM树的差异

比较两颗DOM树的差异是Virtual DOM算法最核心的部分，即Virtual DOM的diff算法。两颗树的完全的diff算法是一个时间复杂度为O(n^3)的问题。但是当中，你很少会跨越层级的移动DOM元素，所以Virtual DOM只会对同一个层级的元素进行对比。这样算法复杂度就可以到O(n)
在实际的代码中，会对新旧两颗树进行一个深度优先的遍历，这样每个节点都会有一个唯一的标记：
每遍历到一个节点就把该节点和新的树进行对比，如果有差异就记录到一个对象里面.

步骤3：把差异应用到真正的DOM树上

因为步骤1所构建的js对象树和render出来真正的DOM树的信息、结构是一样的。所以我们可以对那颗DOM树也进行深度优先的遍历，遍历的时候从步骤2生成的js对象中找出当前遍历的节点差异，然后进行DOM操作

  1. function patch(node, patches){
  2.     var walker = {index: 0};
  3.     dfsWalk(node, walker, patches);
  4. }
  6. function dfsWalk(node, walker, patches){
  7.     var currentPatches = patches[walker.index]; // 从patches拿出当前节点的差异
  9.     var len = node.childrenNodes ? node.childrenNodes.length : 0;
  10.     for (var i = 0; i < len; i++) {// 深度遍历子节点
  11.         var child = node.childrenNodes[i];
  12.         walker.index++;
  13.         dfsWalk(child, walker, patches);
  14.     }
  16.     if (currentPatches){
  17.         applyPatches(node, currentPatches); // 对当前节点进行DOM操作
  18.     }
  19. }

applyPatches，根据不同类型的差异对当前节点进行DOM操作

  1. function applyPatches(node, currentPatches){
  2.     currentPatches.forEach(currentPatch => {
  3.         switch (currentPatch.type) {
  4.             case REPLACE://替换
  5.                 node.parentNode.replaceChild(currentPatch.node.render(), node); //新节点，旧节点
  6.                 break;
  7.             case REORDER://重新排序
  8.                 reorderChildren(node, currentPatch.moves);
  9.                 break;
  10.             case PROPS:
  11.                 setProps(node, currentPatch.props);
  12.                 break;
  13.             case TEXT: 
  14.                 node.textContent = currentPatch.content;
  15.                 break;
  16.             default:
  17.                 throw new Error('Unknown patch type ' + currentPatch.type);
  18.         }
  20.     });
  21. }

使用实例

Virtual DOM算法主要实现上面步骤的三个函数：element、diff、patch

  1. // 1. 构建虚拟DOM
  2. var tree = el('div', {'id': 'container'}, [
  3.     el('h1', {style: 'color: blue'}, ['simple virtal dom']),
  4.     el('p', ['Hello, virtual-dom']),
  5.     el('ul', [el('li')])
  6. ])
  8. // 2. 通过虚拟DOM构建真正的DOM
  9. var root = tree.render()
  10. document.body.appendChild(root)
  12. // 3. 生成新的虚拟DOM
  13. var newTree = el('div', {'id': 'container'}, [
  14.     el('h1', {style: 'color: red'}, ['simple virtal dom']),
  15.     el('p', ['Hello, virtual-dom']),
  16.     el('ul', [el('li'), el('li')])
  17. ]);
  19. // 4. 比较两棵虚拟DOM树的不同
  20. var patches = diff(tree, newTree)
  22. // 5. 在真正的DOM元素上应用变更
  23. patch(root, patches)