虚拟DOM

虚拟 DOM 是一种在内存中构建的、对真实 DOM 的抽象表示。它基于一套算法来优化，通过在 JavaScript 和真实 DOM 之间建立一个缓存，减少不必要的 DOM 操作。因为相比于 DOM 操作，用 JavaScript 操作内存更高效。

简单的过程实现，分为3个步骤

1. 用 JavaScript 对象模拟 DOM 树

用 JavaScript 对象来表示一个 DOM 结构，只需要记录它的节点类型、属性、子节点。

function Element (tagName, props, children) {
  this.tagName = tagName
  this.props = props
  this.children = children
}

module.exports = function (tagName, props, children) {
  return new Element(tagName, props, children)
}

但页面上并没有这个 DOM 结构，要将它渲染成真正的 DOM。

Element.prototype.render = function () {
  var el = document.createElement(this.tagName) // 根据tagName构建
  var props = this.props

  for (var propName in props) { // 设置节点的DOM属性
    var propValue = props[propName]
    el.setAttribute(propName, propValue)
  }

  var children = this.children || []

  children.forEach(function (child) {
    var childEl = (child instanceof Element)
      ? child.render() // 如果子节点也是虚拟DOM，递归构建DOM节点
      : document.createTextNode(child) // 如果字符串，只构建文本节点
    el.appendChild(childEl)
  })

  return el
}

2. 比较两棵虚拟 DOM 树的差异

比较两棵 DOM 树的差异是算法的核心部分，也就是 diff 算法，diff 算法只会对同一层级的元素进行对比，时间复杂度是 O(n)。

深度优先遍历，每遍历到一个节点就将该节点和新的树进行对比，如果有差异就记录到一个 patches 对象中。

// diff 函数，比较两棵虚拟 DOM 树
function diff (oldTree, newTree) {
  var patches = {}; // 用来记录每个节点差异的对象
  walk(oldTree, newTree, patch, 0);
  return patches;
};

// 进行深度优先遍历，并将差异记录到 patches 对象中
function walk (oldNode, newNode, patches, index) {
  // 对比各层级 oldNode 和 newNode 的不同，记录下来
  patches[index] = [...];

  diffChildren(oldNode.children, newNode.children, index, patches);
};

// 遍历子节点
function diffChildren (oldChildren, newChildren, index, patches) {
  var leftNode = null;
  var currentNodeIndex = index;
  oldChildren.forEach(function (child, i) {
    var newChild = newChildren[i];
    currentNodeIndex = (leftNode && leftNode.count) // 计算节点的标识
      ? currentNodeIndex + leftNode.count + 1
      : currentNodeIndex + 1;
    walk(child, newChild, currentNodeIndex, patches); // 深度遍历子节点
    leftNode = child;
  })
};

定义了几种节点差异类型

var REPLACE = 0; // 节点替换
var REORDER = 1; // 节点移动、删除、新增
var PROPS = 2; // 节点属性变化
var TEXT = 3; // 节点文本变化

• 对于节点替换，当新旧节点的 tagName 不一样时，进行节点替换

patches[x] = [{
  type: REPALCE,
  node: newNode
}];

• 对于节点移动、删除、新增，只要层级索引 index 发生变化，将当前节点及其后代节点进行替换，但这样 DOM 操作开销会比较大，为了复用旧的 DOM 树上的节点，使用对比算法进行优化
• 先获取新旧 DOM 树上节点的顺序
• 然后求最小的插入、删除操作，可以参考代码 diff.js
• 最后需要注意的是，因为 tagName 是可重复的，不能用这个来进行对比，需要给子节点加上唯一标识 key，使用key进行对比，这样才能复用旧的 DOM 树上的节点。

patches[x] = [{
  type: REORDER,
  moves: [{remove or insert}, {remove or insert}, ...]
}]

• 对于节点属性变化，记录变化后的属性

patches[x] = [{
  type: PROPS,
  props: {
    id: "001"
  }
}];

• 对于文本节点变化，记录变化后的文本内容

patches[x] = [{
  type: TEXT,
  content: "Hello World"
}]

3. 把差异应用到真实的 DOM 树上

对旧的真实 DOM 也进行深度优先的遍历，遍历的时候从 patches 对象中找出当前遍历的节点差异，然后进行 DOM 操作

function patch (node, patches) {
  var walker = {index: 0}
  walk(node, walker, patches)
}

function walk (node, walker, patches) {
  var currentPatches = patches[walker.index] // 从patches拿出当前节点的差异

  var len = node.childNodes
    ? node.childNodes.length
    : 0
  for (var i = 0; i < len; i++) { // 深度遍历子节点
    var child = node.childNodes[i]
    walker.index++
    walk(child, walker, patches)
  }

  if (currentPatches) {
    applyPatches(node, currentPatches) // 对当前节点进行DOM操作
  }
}

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

function applyPatches (node, currentPatches) {
  currentPatches.forEach(function (currentPatch) {
    switch (currentPatch.type) {
      case REPLACE:
        node.parentNode.replaceChild(currentPatch.node.render(), node)
        break
      case REORDER:
        reorderChildren(node, currentPatch.moves)
        break
      case PROPS:
        setProps(node, currentPatch.props)
        break
      case TEXT:
        node.textContent = currentPatch.content
        break
      default:
        throw new Error('Unknown patch type ' + currentPatch.type)
    }
  })
}