手写DOM diff算法

[iloveyou11]

dom diff的基本概念：
根据两个虚拟dom创建出补丁, 描述改变的内容, 将这个补丁用来更新dom

dom diff的几种优化策略：

1. 更新时只比较同级，并不会跨层比较
2. 同层变化能复用，使用key

实现dom diff算法

我们先写一个主文件，把需要引入的文件和导出的函数列出来，一步步去实现。这里，我们需要创建以下文件：

- index.js（主文件入口）
  1. 创建virtual DOM1、virtual DOM2
  2. 渲染virtual DOM1至页面中
  3. 对比virtual DOM2与virtual DOM1的区别，形成补丁
  4. 拿到补丁去更新视图

- element.js（导出createElement、render、renderDOM方法）
- diff.js（导出diff方法）
- patch.js（导出patch方法）

index.js

在index.js中，我们创建了两个虚拟dom，故意修改了一些属性值、标签名、文本，以测试后面要实现的diff、patch方法。

// 导入其他文件的方法
import {
    createElement,
    render,
    renderDOM
} from './element'
import diff from './diff'
import patch from './patch'

// 写两个virtual DOM
const virtualDOM1 = createElement('ul', {
    class: 'list'
}, [
    createElement('li', {class: 'item'}, ['a']),
    createElement('li', {class: 'item'}, ['b']),
    createElement('li', {class: 'item'}, ['c'])
])
const virtualDOM2 = createElement('ul', {
    class: 'list-group'
}, [
    createElement('li', {class: 'item'}, ['1']),
    createElement('li', {class: 'item'}, ['2']),
    createElement('div', {class: 'item'}, ['c'])
])

// 将virtualDOM1渲染到页面中
const el = render(virtualDOM1)
renderDOM(el, window.root)

// 对比virtualDOM2与virtualDOM1的差异，形成补丁，重新更新视图
const patches = diff(virtualDOM1, virtualDOM2)
patch(el, patches)

首先我们实现其中的createElement（创建虚拟dom）、render（将虚拟dom转化为真实dom）、renderDOM（将元素节点插入到页面上）这几个方法。以下有详细的注释：

element.js

// 虚拟dom元素
class Element {
  constructor(type, props, children) {
    this.type = type
    this.props = props
    this.children = children
  }
}

// 创建虚拟dom
function createElement(type, props, children) {
  return new Element(type, props, children)
}

/**
 * @description 设置属性
 * @param {*} node 页面节点元素
 * @param {*} key 设置属性的类型（修改值？修改样式？修改其他属性？）
 * @param {*} value 设置的新属性值
 */
function setAttr(node, key, value) {
  switch (key) {
    // 1. 修改值
    case 'value':
      if (node.tagName.toLowerCase === 'input' || node.tagName.toLowerCase === 'textarea') {
        node.value = value
      } else {
        node.setAttribute(key, value)
      }
      break
    // 2. 修改样式
    case 'style':
      node.style.cssText = value
      break
    // 3. 修改其他属性
    default:
      node.setAttribute(key, value)
  }
}

// 将虚拟dom转化为真实dom
function render(eleObj) {
  // 根据type创建元素
  let el = document.createElement(eleObj.type)
  // 给元素设置属性
  for (let key in eleObj.props) {
    setAttr(el, key, eleObj.props[key])
  }
  // 如果有子节点，则添加子节点
  eleObj.children.forEach(child => {
    child = (child instanceof Element) ? render(child) : document.createTextNode(child)
    el.appendChild(child)
  })
  return el
}

// 将元素插入到页面内
function renderDOM(el, target) {
  target.appendChild(el)
}

export {
  createElement,
  render,
  Element,
  renderDOM,
  setAttr
}

【注意】在设置元素属性时，因为不同类型的元素设置属性方法不同，因此我们封装了setAttr函数进行统一设置。

目前为止，我们已经实现了创建虚拟dom，并将虚拟dom转化为真实dom渲染到页面中，接下来我们实现核心的diff算法：

首先我们需要制定规则：

1. 如果节点类型相同但是属性不相同，则产生补丁包：{type;'ATTRS',attrs:{class:'list'}}
2. 如果旧dom存在但新dom不存在，则产生补丁包：{type;'REMOVE',index:1}
3. 如果节点类型不相同，直接替换，则产生补丁包：{type;'REPLACE',newNode:newNode}
4. 如果文本内容变化，则产生补丁包：{type;'TEXT',text:'xxx'}

diff.js

// 先分为以下4种类别
const ATTRS = 'ATTRS'
const REMOVE = 'REMOVE'
const REPLACE = 'REPLACE'
const TEXT = 'TEXT'

let Index = 0

const utils = {
  // 工具方法：判断是否是字符串类型
  isString: node => {
    return Object.props.toString.call(node) === '[object String]'
  },

  // 对比新旧属性有哪些变化
  diffAttr: (oldAttrs, newAttrs) => {
    let patch = {}
    // 1. 节点的新属性值和旧属性值不相同
    for (const key in oldAttrs) {
      if (oldAttrs[key] !== newAttrs[key]) {
        patch[key] = newAttrs[key] //有可能是undefined
      }
    }
    // 2. 旧节点没有新节点的某些属性
    for (const key in newAttrs) {
      if (!oldAttrs.hasOwnProperty(key)) {
        patch[key] = newAttrs[key]
      }
    }
    return patch
  },

  // 对比子节点
  diffChildren: (oldChildren, newChildren, patches) => {
    oldChildren.forEach((child, idx) => {
      // index每次传给walk时，index是递增的，定义全局变量Index，所有的基于同一序号实现
      walk(child, newChildren[idx], ++Index, patches)
    });
  }
}

/**
 * @description 深度遍历两棵虚拟dom树，用补丁记录其变更
 * @param {*} oldNode 旧虚拟dom
 * @param {*} newNode 新虚拟dom
 * @param {*} index index序号
 * @param {*} patches 补丁包，记录其变更
 */
function walk(oldNode, newNode, index, patches) {
  let currentPatch = [] //每个元素都有一个补丁对象

  // 1. 新节点被删除
  if (!newNode) {
    currentPatch.push({
      type: REMOVE,
      index
    })
  } else if (utils.isString(oldNode) && utils.isString(newNode)) {
    // 2. 新旧节点都是文本，但是内容发生了变化
    if (oldNode !== newNode) {
      currentPatch.push({
        type: TEXT,
        text: newNode
      })
    }
  } else if (oldNode.nodeType === newNode.nodeType) {
    // 3. 新旧节点的类型相同，但是属性发生了变化
    let attrs = utils.diffAttr(oldNode.props, newNode.props)
    if (Object.keys(attrs).length > 0) {
      currentPatch.pusH({
        TYPE: ATTRS,
        attrs
      })
    }
    utils.diffChildren(oldNode.children, newNode.children, patches) // 如果有子节点,遍历子节点
  } else {
    // 4. 节点被替换
    currentPatch.push({
      type: REPLACE,
      newNode
    })
  }
  //当前元素确实有补丁
  if (currentPatch.length > 0) { 
    // 将元素和补丁对应起来,放到大补丁包中
    patches[index] = currentPatch
  }
}

// 深度遍历两棵虚拟dom树，生成最终的大补丁包patches
function diff(oldTree, newTree) {
  let patches = {}
  let index = 0
  walk(oldTree, newTree, index, patches)
  return patches
}

export default diff

通过diff方法，我们能对两个虚拟dom产生完整的patches对象（详细记录了更改信息），以便后续的更新操作。接下来，我们实现patch方法，根据patches对象，完成真实dom的更新工作：

patch.js

import {
  Element,
  render,
  setAttr
} from './element'

let index = 0

// diff分为以下4种类别
const ATTRS = 'ATTRS'
const REMOVE = 'REMOVE'
const REPLACE = 'REPLACE'
const TEXT = 'TEXT'

// 根据当前节点的补丁包去更新此节点
function _doPatch(node, patches) {
  patches.forEach(patch => {
    // 根据patch的不同type决定如何去更新dom
    switch (patch.type) {
      // 1. 属性变更
      case ATTRS:
        for (const key in patch.attrs) {
          let value = patch.attrs[key]
          if (value) {
            setAttr(node, key, value)
          } else { // 如果属性值为undefined则直接删除属性（因为旧节点有此属性但新节点没有时，这里的值为undefined）
            node.removeAttribute(key)
          }
        }
        break

      // 2. 节点移除
      case REMOVE:
        node.parentNode.removeChild(node)
        break

      // 3. 节点替换
      case REPLACE:
        let newNode = patch.newNode instanceof Element ? render(patch.newNode) : document.createTextNode(patch.newNode)
        node.parentNode.replaceChild(newNode, node)
        break

      // 4. 文本更改
      case TEXT:
        node.textContent = patch.text
        break
    }
  })
}

// 导出patch函数
function patch(node, patches) {
  let currentPatch = patches[index++] // 拿到当前节点的补丁包
  let childNodes = node.childNodes // 拿到当前节点的子节点
  // 遍历子节点
  childNodes.forEach(child => {
    _walk(child)
  });
  // 根据当前节点的补丁包去更新此节点
  if (currentPatch) {
    _doPatch(node, currentPatch)
  }
}

export default patch

终于完成啦！可以愉快地使用index.js进行测试了~

但是此时的dom diff策略还有很多需要优化的地方，例如：

1. 如果同级只是交换节点位置，会导致重新渲染（应该只是交换位置），这时应该考虑到key标识减少重复渲染
2. 新增节点也不会被更新
3. ……

后期将继续完善dom diff策略~