Virtual Dom

代码地址

为什么需要 Virtual Dom

众所周知，操作 DOM 是很耗费性能的一件事情，既然如此，我们可以考虑通过 JS 对象来模拟 DOM 对象，毕竟操作 JS 对象比操作 DOM 省时的多。

举个例子

  1. // 假设这里模拟一个 ul，其中包含了 5 个 li
  2. [1, 2, 3, 4, 5]
  3. // 这里替换上面的 li
  4. [1, 2, 5, 4]

从上述例子中，我们一眼就可以看出先前的 ul 中的第三个 li 被移除了，四五替换了位置。

如果以上操作对应到 DOM 中，那么就是以下代码

  1. // 删除第三个 li
  2. ul.childNodes[2].remove()
  3. // 将第四个 li 和第五个交换位置
  4. let fromNode = ul.childNodes[4]
  5. let toNode = node.childNodes[3]
  6. let cloneFromNode = fromNode.cloneNode(true)
  7. let cloenToNode = toNode.cloneNode(true)
  8. ul.replaceChild(cloneFromNode, toNode)
  9. ul.replaceChild(cloenToNode, fromNode)

当然在实际操作中，我们还需要给每个节点一个标识，作为判断是同一个节点的依据。所以这也是 Vue 和 React 中官方推荐列表里的节点使用唯一的 key 来保证性能。

那么既然 DOM 对象可以通过 JS 对象来模拟，反之也可以通过 JS 对象来渲染出对应的 DOM

以下是一个 JS 对象模拟 DOM 对象的简单实现

  1. export default class Element {
  2.   /**
  3.    * @param {String} tag 'div'
  4.    * @param {Object} props { class: 'item' }
  5.    * @param {Array} children [ Element1, 'text']
  6.    * @param {String} key option
  7.    */
  8.   constructor(tag, props, children, key) {
  9.     this.tag = tag
  10.     this.props = props
  11.     if (Array.isArray(children)) {
  12.       this.children = children
  13.     } else if (isString(children)) {
  14.       this.key = children
  15.       this.children = null
  16.     }
  17.     if (key) this.key = key
  18.   }
  19.   // 渲染
  20.   render() {
  21.     let root = this._createElement(
  22.       this.tag,
  23.       this.props,
  24.       this.children,
  25.       this.key
  26.     )
  27.     document.body.appendChild(root)
  28.     return root
  29.   }
  30.   create() {
  31.     return this._createElement(this.tag, this.props, this.children, this.key)
  32.   }
  33.   // 创建节点
  34.   _createElement(tag, props, child, key) {
  35.     // 通过 tag 创建节点
  36.     let el = document.createElement(tag)
  37.     // 设置节点属性
  38.     for (const key in props) {
  39.       if (props.hasOwnProperty(key)) {
  40.         const value = props[key]
  41.         el.setAttribute(key, value)
  42.       }
  43.     }
  44.     if (key) {
  45.       el.setAttribute('key', key)
  46.     }
  47.     // 递归添加子节点
  48.     if (child) {
  49.       child.forEach(element => {
  50.         let child
  51.         if (element instanceof Element) {
  52.           child = this._createElement(
  53.             element.tag,
  54.             element.props,
  55.             element.children,
  56.             element.key
  57.           )
  58.         } else {
  59.           child = document.createTextNode(element)
  60.         }
  61.         el.appendChild(child)
  62.       })
  63.     }
  64.     return el
  65.   }
  66. }

Virtual Dom 算法简述

既然我们已经通过 JS 来模拟实现了 DOM，那么接下来的难点就在于如何判断旧的对象和新的对象之间的差异。

DOM 是多叉树的结构，如果需要完整的对比两颗树的差异，那么需要的时间复杂度会是 O(n ^ 3)，这个复杂度肯定是不能接受的。于是 React 团队优化了算法，实现了 O(n) 的复杂度来对比差异。

实现 O(n) 复杂度的关键就是只对比同层的节点，而不是跨层对比，这也是考虑到在实际业务中很少会去跨层的移动 DOM 元素。

所以判断差异的算法就分为了两步

  • 首先从上至下，从左往右遍历对象，也就是树的深度遍历，这一步中会给每个节点添加索引，便于最后渲染差异
  • 一旦节点有子元素，就去判断子元素是否有不同

Virtual Dom 算法实现

树的递归

首先我们来实现树的递归算法，在实现该算法前，先来考虑下两个节点对比会有几种情况

  1. 新的节点的 tagName 或者 key 和旧的不同，这种情况代表需要替换旧的节点，并且也不再需要遍历新旧节点的子元素了，因为整个旧节点都被删掉了
  2. 新的节点的 tagName 和 key（可能都没有）和旧的相同，开始遍历子树
  3. 没有新的节点，那么什么都不用做
  1. import { StateEnums, isString, move } from './util'
  2. import Element from './element'
  4. export default function diff(oldDomTree, newDomTree) {
  5.   // 用于记录差异
  6.   let pathchs = {}
  7.   // 一开始的索引为 0
  8.   dfs(oldDomTree, newDomTree, 0, pathchs)
  9.   return pathchs
  10. }
  12. function dfs(oldNode, newNode, index, patches) {
  13.   // 用于保存子树的更改
  14.   let curPatches = []
  15.   // 需要判断三种情况
  16.   // 1.没有新的节点，那么什么都不用做
  17.   // 2.新的节点的 tagName 和 `key` 和旧的不同，就替换
  18.   // 3.新的节点的 tagName 和 key（可能都没有） 和旧的相同，开始遍历子树
  19.   if (!newNode) {
  20.   } else if (newNode.tag === oldNode.tag && newNode.key === oldNode.key) {
  21.     // 判断属性是否变更
  22.     let props = diffProps(oldNode.props, newNode.props)
  23.     if (props.length) curPatches.push({ type: StateEnums.ChangeProps, props })
  24.     // 遍历子树
  25.     diffChildren(oldNode.children, newNode.children, index, patches)
  26.   } else {
  27.     // 节点不同，需要替换
  28.     curPatches.push({ type: StateEnums.Replace, node: newNode })
  29.   }
  31.   if (curPatches.length) {
  32.     if (patches[index]) {
  33.       patches[index] = patches[index].concat(curPatches)
  34.     } else {
  35.       patches[index] = curPatches
  36.     }
  37.   }
  38. }

判断属性的更改

判断属性的更改也分三个步骤

  1. 遍历旧的属性列表，查看每个属性是否还存在于新的属性列表中
  2. 遍历新的属性列表，判断两个列表中都存在的属性的值是否有变化
  3. 在第二步中同时查看是否有属性不存在与旧的属性列列表中
  1. function diffProps(oldProps, newProps) {
  2.   // 判断 Props 分以下三步骤
  3.   // 先遍历 oldProps 查看是否存在删除的属性
  4.   // 然后遍历 newProps 查看是否有属性值被修改
  5.   // 最后查看是否有属性新增
  6.   let change = []
  7.   for (const key in oldProps) {
  8.     if (oldProps.hasOwnProperty(key) && !newProps[key]) {
  9.       change.push({
  10.         prop: key
  11.       })
  12.     }
  13.   }
  14.   for (const key in newProps) {
  15.     if (newProps.hasOwnProperty(key)) {
  16.       const prop = newProps[key]
  17.       if (oldProps[key] && oldProps[key] !== newProps[key]) {
  18.         change.push({
  19.           prop: key,
  20.           value: newProps[key]
  21.         })
  22.       } else if (!oldProps[key]) {
  23.         change.push({
  24.           prop: key,
  25.           value: newProps[key]
  26.         })
  27.       }
  28.     }
  29.   }
  30.   return change
  31. }

判断列表差异算法实现

这个算法是整个 Virtual Dom 中最核心的算法，且让我一一为你道来。这里的主要步骤其实和判断属性差异是类似的，也是分为三步

  1. 遍历旧的节点列表，查看每个节点是否还存在于新的节点列表中
  2. 遍历新的节点列表，判断是否有新的节点
  3. 在第二步中同时判断节点是否有移动

PS：该算法只对有 key 的节点做处理

  1. function listDiff(oldList, newList, index, patches) {
  2.   // 为了遍历方便，先取出两个 list 的所有 keys
  3.   let oldKeys = getKeys(oldList)
  4.   let newKeys = getKeys(newList)
  5.   let changes = []
  7.   // 用于保存变更后的节点数据
  8.   // 使用该数组保存有以下好处
  9.   // 1.可以正确获得被删除节点索引
  10.   // 2.交换节点位置只需要操作一遍 DOM
  11.   // 3.用于 `diffChildren` 函数中的判断，只需要遍历
  12.   // 两个树中都存在的节点，而对于新增或者删除的节点来说，完全没必要
  13.   // 再去判断一遍
  14.   let list = []
  15.   oldList &&
  16.     oldList.forEach(item => {
  17.       let key = item.key
  18.       if (isString(item)) {
  19.         key = item
  20.       }
  21.       // 寻找新的 children 中是否含有当前节点
  22.       // 没有的话需要删除
  23.       let index = newKeys.indexOf(key)
  24.       if (index === -1) {
  25.         list.push(null)
  26.       } else list.push(key)
  27.     })
  28.   // 遍历变更后的数组
  29.   let length = list.length
  30.   // 因为删除数组元素是会更改索引的
  31.   // 所有从后往前删可以保证索引不变
  32.   for (let i = length - 1; i >= 0; i--) {
  33.     // 判断当前元素是否为空，为空表示需要删除
  34.     if (!list[i]) {
  35.       list.splice(i, 1)
  36.       changes.push({
  37.         type: StateEnums.Remove,
  38.         index: i
  39.       })
  40.     }
  41.   }
  42.   // 遍历新的 list，判断是否有节点新增或移动
  43.   // 同时也对 `list` 做节点新增和移动节点的操作
  44.   newList &&
  45.     newList.forEach((item, i) => {
  46.       let key = item.key
  47.       if (isString(item)) {
  48.         key = item
  49.       }
  50.       // 寻找旧的 children 中是否含有当前节点
  51.       let index = list.indexOf(key)
  52.       // 没找到代表新节点，需要插入
  53.       if (index === -1 || key == null) {
  54.         changes.push({
  55.           type: StateEnums.Insert,
  56.           node: item,
  57.           index: i
  58.         })
  59.         list.splice(i, 0, key)
  60.       } else {
  61.         // 找到了，需要判断是否需要移动
  62.         if (index !== i) {
  63.           changes.push({
  64.             type: StateEnums.Move,
  65.             from: index,
  66.             to: i
  67.           })
  68.           move(list, index, i)
  69.         }
  70.       }
  71.     })
  72.   return { changes, list }
  73. }
  75. function getKeys(list) {
  76.   let keys = []
  77.   let text
  78.   list &&
  79.     list.forEach(item => {
  80.       let key
  81.       if (isString(item)) {
  82.         key = [item]
  83.       } else if (item instanceof Element) {
  84.         key = item.key
  85.       }
  86.       keys.push(key)
  87.     })
  88.   return keys
  89. }

遍历子元素打标识

对于这个函数来说，主要功能就两个

  1. 判断两个列表差异
  2. 给节点打上标记

总体来说，该函数实现的功能很简单

  1. function diffChildren(oldChild, newChild, index, patches) {
  2.   let { changes, list } = listDiff(oldChild, newChild, index, patches)
  3.   if (changes.length) {
  4.     if (patches[index]) {
  5.       patches[index] = patches[index].concat(changes)
  6.     } else {
  7.       patches[index] = changes
  8.     }
  9.   }
  10.   // 记录上一个遍历过的节点
  11.   let last = null
  12.   oldChild &&
  13.     oldChild.forEach((item, i) => {
  14.       let child = item && item.children
  15.       if (child) {
  16.         index =
  17.           last && last.children ? index + last.children.length + 1 : index + 1
  18.         let keyIndex = list.indexOf(item.key)
  19.         let node = newChild[keyIndex]
  20.         // 只遍历新旧中都存在的节点，其他新增或者删除的没必要遍历
  21.         if (node) {
  22.           dfs(item, node, index, patches)
  23.         }
  24.       } else index += 1
  25.       last = item
  26.     })
  27. }

渲染差异

通过之前的算法，我们已经可以得出两个树的差异了。既然知道了差异，就需要局部去更新 DOM 了，下面就让我们来看看 Virtual Dom 算法的最后一步骤

这个函数主要两个功能

  1. 深度遍历树，将需要做变更操作的取出来
  2. 局部更新 DOM

整体来说这部分代码还是很好理解的

  1. let index = 0
  2. export default function patch(node, patchs) {
  3.   let changes = patchs[index]
  4.   let childNodes = node && node.childNodes
  5.   // 这里的深度遍历和 diff 中是一样的
  6.   if (!childNodes) index += 1
  7.   if (changes && changes.length && patchs[index]) {
  8.     changeDom(node, changes)
  9.   }
  10.   let last = null
  11.   if (childNodes && childNodes.length) {
  12.     childNodes.forEach((item, i) => {
  13.       index =
  14.         last && last.children ? index + last.children.length + 1 : index + 1
  15.       patch(item, patchs)
  16.       last = item
  17.     })
  18.   }
  19. }
  21. function changeDom(node, changes, noChild) {
  22.   changes &&
  23.     changes.forEach(change => {
  24.       let { type } = change
  25.       switch (type) {
  26.         case StateEnums.ChangeProps:
  27.           let { props } = change
  28.           props.forEach(item => {
  29.             if (item.value) {
  30.               node.setAttribute(item.prop, item.value)
  31.             } else {
  32.               node.removeAttribute(item.prop)
  33.             }
  34.           })
  35.           break
  36.         case StateEnums.Remove:
  37.           node.childNodes[change.index].remove()
  38.           break
  39.         case StateEnums.Insert:
  40.           let dom
  41.           if (isString(change.node)) {
  42.             dom = document.createTextNode(change.node)
  43.           } else if (change.node instanceof Element) {
  44.             dom = change.node.create()
  45.           }
  46.           node.insertBefore(dom, node.childNodes[change.index])
  47.           break
  48.         case StateEnums.Replace:
  49.           node.parentNode.replaceChild(change.node.create(), node)
  50.           break
  51.         case StateEnums.Move:
  52.           let fromNode = node.childNodes[change.from]
  53.           let toNode = node.childNodes[change.to]
  54.           let cloneFromNode = fromNode.cloneNode(true)
  55.           let cloenToNode = toNode.cloneNode(true)
  56.           node.replaceChild(cloneFromNode, toNode)
  57.           node.replaceChild(cloenToNode, fromNode)
  58.           break
  59.         default:
  60.           break
  61.       }
  62.     })
  63. }

最后

Virtual Dom 算法的实现也就是以下三步

  1. 通过 JS 来模拟创建 DOM 对象
  2. 判断两个对象的差异
  3. 渲染差异
  1. let test4 = new Element('div', { class: 'my-div' }, ['test4'])
  2. let test5 = new Element('ul', { class: 'my-div' }, ['test5'])
  4. let test1 = new Element('div', { class: 'my-div' }, [test4])
  6. let test2 = new Element('div', { id: '11' }, [test5, test4])
  8. let root = test1.render()
  10. let pathchs = diff(test1, test2)
  11. console.log(pathchs)
  13. setTimeout(() => {
  14.   console.log('开始更新')
  15.   patch(root, pathchs)
  16.   console.log('结束更新')
  17. }, 1000)

当然目前的实现还略显粗糙，但是对于理解 Virtual Dom 算法来说已经是完全足够的了。