Back
Featured image of post 虚拟 DOM 和 DOM diff

虚拟 DOM 和 DOM diff

作为前端,相信对于 DOM 已经很熟悉了。DOM 就是文档对象模型,是 HTML 和 XML 文档的编程接口,它是一个树结构,提供了对文档的结构化的表述,并定义了一种方式可以使从程序中对该结构进行访问。

那什么是 虚拟 DOM 呢?

虚拟 DOM

虚拟 DOM (Virtual DOM) 是 JavaScript 中的一个 对象 ,使用该对象模拟 DOM 节点,最后使用特定的 Render 方法将该对象渲染为真实的 DOM。

优点

  • 虚拟 DOM 本质是一个 JavaScript 对象,所以它不仅可以映射 HTML 的 DOM,还可以扩展到 小程序、原生应用 等其他平台。
  • 可以通过 DOM Diff 算法来优化 DOM 操作。通过 Diff 合并多余操作进而提高了性能。

缺点

由于虚拟 DOM 是一个对象,所以它不能直接渲染到页面上,需要使用特定的 Render 方法来渲染。例如 React 中的 createElement 方法,Vue 中的 h 方法等。

  • React
// createElement(type, props, children)
const element = React.createElement(
  'div',
  { className: 'foo' },
  'Hello World'
);

// jsx
const element = <div className="foo">Hello World</div>;
  • Vue
// h(type, props, children)const element = h('div', { className: 'foo' }, 'Hello World');

// jsxconst element =
<div className = "foo">Hello World</div>;

DOM Diff

DOM diff 就是对虚拟 DOM 的对比算法,Dom diff,通过 JS 层面的计算,返回一个 patch 对象,即补丁对象,再通过特定的操作解析 patch 对象,省略不必要的操作,完成页面的重新渲染,提高页面渲染性能。

在 jQuery 时代,都是用我们自己业务的一些算法,手动进行 DOM 的操作,比如我们调用的 .append.remove 之类的方法。

这样的问题很明显,就是业务心智负担太重,对于复杂系统,需要做 Diff 的地方太多,不仅写起来繁琐,当状态存在交错时,手动 Dom Diff 容易出现遗漏,Bug 甚至程序崩溃,代码的可维护性也很差。

解决方案就是数据驱动视图,我们只需要关注数据和 UI 如何映射,具体的 DOM 操作由框架进行操作,这样无论业务逻辑多复杂,我们只需要解决映射关系就可以了。目前前端的框架主流已经从面向操作转变为数据驱动视图,这样框架就必须作 DOM Diff 算法来优化 DOM 操作,否则容易引发性能问题。

理想的 DOM Diff

最理想的 Dom diff 自然是复用所有能复用的,实在遇到新增或删除时,才执行插入或删除。可惜程序无法猜到人的想法,所以想要精确复用的话,在某些情况下时间复杂度会很离谱 - O(n³) ,这显然对于性能的消耗是巨大的,因此无法被使用。

现实的 DOM Diff

Vue 的 DOM Diff 是 深度优先,同层比较 的策略。

Vue 的 Diff
Vue 的 Diff

新节点与旧节点的比较主要是围绕三件事来达到渲染目的:

创建新节点

当新树包含旧树没有的节点,此时直接创建新节点。只有元素节点,文本节点,注释节点才能被创建插入到 DOM 中。

删除旧节点

当旧树包含新树没有的节点,意味着新树放弃了旧树的一部分,此时直接删除桕树多出的节点,删除节点会连带的删除节点的子节点。

更新节点

新的节点与旧的的节点都有,那么以新的为准,更新旧节点。如何判断是否需要更新节点呢?

  • 完全一致的话就不需要更新
// 判断vnode与oldVnode是否完全一样
if (oldVnode === vnode){
  return;
}
  • 判断新节点与旧节点是否是静态节点,key 是否一样,是否是克隆节点(如果不是克隆节点,那么意味着渲染函数被重置了,这个时候需要重新渲染) 或者是否设置了 once 属性,满足条件的话替换 componentInstance
// 是否是静态节点,key是否一样,是否是克隆节点或者是否设置了once属性
if (
  isTrue(vnode.isStatic) &&
  isTrue(oldVnode.isStatic) &&
  vnode.key === oldVnode.key &&
  (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
){
  vnode.componentInstance = oldVnode.componentInstance;
  return;
}
  • 判断新节点是否有 text,如果有那么需要比较同层级旧节点,如果旧节点文本不同于新节点文本,那么采用新的文本内容。如果新节点没有文本,那么后面需要对子节点的相关情况进行判断
// 判断新节点是否有文本
if (isUndef(vnode.text)){
  // 如果没有文本,处理子节点的相关代码
  // ......
} else if (oldVnode.text !== vnode.text){
  // 新节点文本替换旧节点文本
  nodeOps.setTextContent(elm, vnode.text)
}
  • 判断新节点与旧节点的子节点相关状况。新增和删除逻辑与上面基本一致,都不存在子节点则不用处理子节点。如果都存在子节点,则需要进行 Diff,这里的重点就是子节点的 比较更新(updateChildren,Vue 主要是双端比较。

比较更新 updateChildren

新旧节点都有子节点的情况下,这个时候是需要调用 updateChildren 方法来比较更新子节点的。所以在数据上,新旧节点子节点,就保存为了两个数组。子节点更新采用的是 双端比较 的策略,就是新旧节点比较是通过互相比较首尾元素,然后向中间靠拢比较(newStartIdx、oldStartIdx递增,newEndIdx、oldEndIdx递减)的策略。

const oldCh = [oldVnode1, oldVnode2, oldVnode3];
const newCh = [newVnode1, newVnode2, newVnode3];

双端比较
双端比较

向中间靠拢
向中间靠拢

子节点比较过程

  • 新前 与 旧前 比较,如果他们相同,那么进行上面说到的 patch VNode 更新操作,然后新旧节点各向后一步,进行第二项的比较,直到遇到不同则切换下一种比较方式
if (sameVnode(oldStartVnode, newStartVnode)){
  // 更新子节点
  patchVnode(
    oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
  // 新旧各向后一步
  oldStartVnode = oldCh[++ oldStartIdx]
  newStartVnode = newCh[++ newStartIdx]
}
  • 新后 与 旧后 比较,如果他们相同,同样进行 patch VNode 更新,然后新旧各向前一步,进行前一项的比较,直到遇到不同则切换下一种比较方式
if (sameVnode(oldEndVnode, newEndVnode)){
  //更新子节点
  patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
  // 新旧向前
  oldEndVnode = oldCh[-- oldEndIdx]
  newEndVnode = newCh[-- newEndIdx]
}
  • 新后 与 旧前 比较,如果它们相同,就进行更新操作,然后将 旧前 移动到 所有未处理旧节点数组 最后面,使旧前与新后位置保持一致,然后新向前,旧向后,一起向中间靠拢。如果不同会继续切换比较方式
if (sameVnode(oldStartVnode, newEndVnode)){
  patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
  //将旧子节点数组第一个子节点移动插入到最后
  canMove && nodeOps.insertBefore(
    parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
  //旧向后
  oldStartVnode = oldCh[++ oldStartIdx]
  //新向前
  newEndVnode = newCh[-- newEndIdx]
  • 新前 与 旧后 比较,如果他们相同,就进行更新,然后将 旧后 移动到 所有未处理旧节点数组 最前面 ,使旧后与新前位置保持一致,然后新向后,旧向前,一起向中间靠拢,继续比较剩余的节点。如果不同,就使用传统的循环遍历查找。
if (sameVnode(oldEndVnode, newStartVnode)){
  patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
  //将旧后移动插入到最前
  canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
  //旧向前
  oldEndVnode = oldCh[-- oldEndIdx]
  //新向后
  newStartVnode = newCh[++ newStartIdx]
}
  • 循环遍历查找,上面四种都没找到的情况下,会通过key去查找匹配。

进行到这一步对于没有设置 key 的节点,第一次会通过 createKeyToOldIdx 建立 key 与 index 的映射 { key: index }

// 对于没有设置key的节点,第一次会通过createKeyToOldIdx建立key与index的映射 {key:index}
if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(
  oldCh, oldStartIdx, oldEndIdx)

然后拿新节点的key与旧节点进行比较,找到 key 值匹配的节点的位置,这里需要注意的是,如果新节点也没 key,那么就会执行 findIdxInOld 方法,从头到尾遍历匹配旧节点

//通过新节点的key,找到新节点在旧节点中所在的位置下标,如果没有设置key,会执行遍历操作寻找
idxInOld = isDef(newStartVnode.key)
  ? oldKeyToIdx[newStartVnode.key]
  : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)

//findIdxInOld方法
function findIdxInOld (node, oldCh, start, end){
  for (let i = start; i < end; i ++){
    const c = oldCh[i]
    //找到相同节点下标
    if (isDef(c) && sameVnode(node, c)) return i
  }
}

如果通过上面的方法,依旧没找到新节点与旧节点匹配的下标,那就说明这个节点是新节点,那就执行新增的操作。

//如果新节点无法在旧节点中找到自己的位置下标,说明是新元素,执行新增操作
if (isUndef(idxInOld)){
  createElm(
    newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false,
    newCh, newStartIdx
  )
}

如果找到了,那么说明在旧节点中找到了 key 值一样,或者节点和 key 都一样的旧节点。如果节点一样,那么在 patch VNode 之后,需要将旧节点移动到所有未处理节点之前,对于 key 一样,元素不同的节点,将其认为是新节点,执行新增操作。执行完成后,新节点向后一步。

//如果新节点无法在旧节点中找到自己的位置下标,说明是新元素,执行新增操作
if (isUndef(idxInOld)){
  // 新增元素
  createElm(
    newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false,
    newCh, newStartIdx
  )
} else{
  // 在旧节点中找到了key值一样的节点
  vnodeToMove = oldCh[idxInOld]
  if (sameVnode(vnodeToMove, newStartVnode)){
    // 相同子节点更新操作
    patchVnode(
      vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
    // 更新完将旧节点赋值undefined
    oldCh[idxInOld] = undefined
    //将旧节点移动到所有未处理节点之前
    canMove && nodeOps.insertBefore(
      parentElm, vnodeToMove.elm, oldStartVnode.elm)
  } else{
    // 如果是相同的key,不同的元素,当做新节点,执行创建操作
    createElm(
      newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false,
      newCh, newStartIdx
    )
  }
}
//新节点向后
newStartVnode = newCh[++ newStartIdx]

当完成对旧节点的遍历,但是新节点还没完成遍历,那就说明后续的都是新增节点,执行新增操作,如果完成对新节点遍历,旧节点还没完成遍历,那么说明旧节点出现冗余节点,执行删除操作。

//完成对旧节点的遍历,但是新节点还没完成遍历,
if (oldStartIdx > oldEndIdx){
  refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
  // 新增节点
  addVnodes(
    parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
} else if (newStartIdx > newEndIdx){
  // 发现多余的旧节点,执行删除操作
  removeVnodes(oldCh, oldStartIdx, oldEndIdx)
}

上面就是子节点比较更新的一个完整过程

参考资料

Virtual DOM 与 diff

渲染页面:浏览器的工作原理

Vue 中的 DOM-Diff

深入剖析:Vue 核心之虚拟 DOM

详解虚拟 DOM 与 Diff 算法