浅谈 Virtual Dom

抛开vue、react中的virtual dom，来聊下我们怎么去实现一个差不多还能凑合的 virtual dom。

思考下virtual dom应该做什么事情

先要有能造出一颗树的工具，这颗能用 js 描述出来的树
有一个转换方法，把那颗树转换为真实的dom
再有一个对比机制，找出新旧差异
把新旧差异再更新到真实dom中

来一颗树

这颗树长啥样啊？上面的叶子是啥样的？
叶子还能是啥，element 呗？
嗯...
先来一个能表示唯一标示的属性呗
key?
差不多这意思吧...，再来个类型?
type?
嗯好，元素上还有一堆属性呢...
那就 attrs?
好low… 还可能有一堆孩子
children 咯

so...

{
  key: 'emmmm.....',
  type: 'div',
  attrs: {
    class: 'container',
    'data-type': 'string'
  },
  children: [
    {
      key: 'hkask',
      type: 'h2',
      attrs: {},
      text: 'virtual dom'
    },
    {
      key: 'sdashdjk',
      type: 'div',
      text: '一会被移除1'
    },
    {
      key: 'hfkjahfk',
      type: 'span',
      arrts: {},
      text: '什么是virtual dom啊'
    },
    {
      key: 'sdashdjk2133',
      type: 'div',
      text: '一会被移除2'
    },
  ]
}

说明
比如有课树的顺序是: 1、3、5、7
新的树可以是：1、3、4、5、7
但不会是 1、5、3、7
一旦插入到整颗树中，前后顺序不会再发生变化

转换

假树有了，那就变成真的:

注意:这里有text属性并且text不为空，就表示该节点为文本节点，有文本节点就不考虑其children属性

function render(element) {
  // 先根据type创建元素
  const el = document.createElement(element.type)
  // 再添加 元素属性
  for (let attr in element.arrts) {
    // 这里不考虑 input 和 textarea 的value属性情况了
    element.setAttribute(attr, element.arrts[attr])
  }

  // 判断子元素是不是文本类型的
  if (element.text) {
    el.appendChild(document.createTextNode(element.text))
  } else {
    // 遍历子元素
    element.children &&
      element.children.forEach((val) => {
        el.appendChild(render(val))
      })
  }

  element.$el = el

  return el
}

这里会给 element 属性增加一个 $el 属性，这样整个dom树就在虚拟树上关联起来了。

dom diff

比如在vue中，data 属性中有变化，重新生成了一个新的树

那就开始diff一下，那 diff 啥了？

先比较根节点
比较 key 、比较 type 、比较 attrs、比较children
比较 children 中的 key 、type、attrs 、children
然后循环...

这里比较的方案是 snabbdom 中的简版, 但思路是一样的

在 snabbdom 中先比较同层级的元素，然后比较相同元素的子元素。

比较根节点

function patch(oldNode, newNode) {
  if (sameNode(oldNode, newNode)) {
    // 类型一致 比较里面的内容
    patchNode(oldNode, newNode)
  } else {
    // 不一致删除旧的， 添加新的dom
    const parentEl = oldNode.$el.parentElement
    parentEl.replaceChild(render(newNode), oldNode.$el)
  }

  return newNode
}

比较根节点中的具体细节

function patchNode(oldNode, newNode) {
  newNode.$el = oldNode.$el
  // 判断属性是否需要更新
  if (newNode.text) {
    // 更新文本节点
    if (newNode.text !== oldNode.text) newNode.$el.innerHTML = ''
    newNode.$el.appendChild(document.createTextNode(newNode.text))
    return
  }
  // 如果都有子节点
  if (oldNode.children && newNode.children) {
    // 比较子节点
    updateChildren(newNode.$el, oldNode.children, newNode.children)
  } else if (oldNode.children) {
    // 如果旧的有 新的没有 删除旧的子节点
    newNode.$el.innerHTML = ''
  } else if (newNode.children) {
    // 如果新的有 旧的没有 添加新的子节点
    newNode.children.forEach((val) => {
      newNode.appendChild(render(element))
    })
  }
}

比较子节点

在snabbdom中还有各种事件,比如元素添加、更新、删除之类的。
这里简版实现不存在这些...

这里逻辑比较绕…

snabbdom 中算法还是比较牛逼的… 新旧前后交叉比较

大概逻辑：

旧的第一个和新的第一个比较
如果不匹配旧的第一个和新的最后一个比较
如果不匹配旧的最后一个和新的最后一个比较
如果不匹配旧的最后一个和新的第一个比较
如果还不匹配，查找新的第一个的key 在旧的children中的位置
然后比较类型
如果没找到说明新的第一个是新增加的

function updateChildren(parentElement, oldCh, newCh) {
  let oldStartIndex = 0,
    newStartIndex = 0,
    oldEndIndex = oldCh.length - 1,
    newEndIdnex = newCh.length - 1
  let oldStartNode = oldCh[0],
    newStartNode = newCh[0]
  let oldEndNode = oldCh[oldEndIndex],
    newEndNode = newCh[newEndIdnex]
  let oldKeyMap = ''

  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIdnex) {
    if (!oldStartNode) {
      oldStartNode = oldCh[++oldStartIndex]
    } else if (!newStartNode) {
      newStartNode = newCh[++newStartIndex]
    } else if (!oldEndNode) {
      oldEndNode = oldCh[--oldEndIndex]
    } else if (!newEndNode) {
      newEndNode = newCh[--newEndIdnex]
    } else if (sameNode(oldStartNode, newStartNode)) {
      patchNode(oldStartNode, newStartNode)
      oldStartNode = oldCh[++oldStartIndex]
      newStartNode = newCh[++newStartIndex]
    } else if (sameNode(oldEndNode, newEndNode)) {
      patchNode(oldEndNode, newEndNode)
      oldEndNode = oldCh[--oldEndIndex]
      newEndNode = newCh[--newEndIdnex]
    } else if (sameNode(oldStartNode, newEndNode)) {
      patchNode(oldStartNode, newEndNode)
      oldStartNode = oldCh[++oldStartIndex]
      newEndNode = newCh[--newEndIdnex]
    } else if (sameNode(oldEndNode, newStartNode)) {
      patchNode(oldEndNode, newStartNode)
      oldEndNode = oldCh[--oldEndIndex]
      newStartNode = newCh[++newStartIndex]
    } else {
      // 如果交叉比较都不一样, 根据 key 找到元素对应的位置

      if (!oldKeyMap) {
        oldKeyMap = createOldKeyMap(oldCh, oldStartIndex, oldEndIndex)
      }

      // 看看 newStartNode 的 key 在老节点树中能否找到
      let oldKeyIndex = oldKeyMap[newStartNode.key]

      if (oldKeyIndex !== undefined) {
        // 找到了
        let currentOldNode = oldCh[oldKeyIndex]
        if (currentOldNode.type !== newStartNode.type) {
          // 类型不一致 把新的节点 插入到 旧的前面
          parentElement.insertBefore(render(newStartNode), oldStartNode.$el)
        } else {
          // 类型一直 比较其他内容，并删除旧节点
          patchNode(currentOldNode, newStartNode)
          oldCh[oldKeyIndex] = undefined
        }

        newStartNode = newCh[++newStartIndex]
      } else {
        // 没有找到 说明是新增的，在插入 oldStartNode 前插入
        console.log(oldStartNode.$el)
        parentElement.insertBefore(render(newStartNode), oldStartNode.$el)

        newStartNode = newCh[++newStartIndex]
      }
    }
  }
  if (oldStartIndex <= oldEndIndex || newStartIndex <= newEndIdnex) {
    // 有一个树遍历完了，另一个没有遍历完的情况
    if (oldStartIndex > oldEndIndex) {
      // 旧的树遍历完了，新的没遍历完 添加中间的
      addNodes(parentElement, newCh[newEndIdnex + 1].$el, newStartIndex, newEndIdnex)
    } else {
      // 新的遍历完了，移除旧的树
      removeNodes(parentElement, oldCh, oldStartIndex, oldEndIndex)
    }
  }
}