评论

Vue Diff 算法解析

了解vue diff 的过程能更加高效的使用框架,或者遇到bug时可以往更加底层的方向上思考。

目录

  • 前言
  • Virtual Dom
  • 分析 Diff
  • 总结

Vue 2.0引入Vertial Dom,主要目的是减少 DOM 的操作,高效利用旧的 DOM 节点处理模板的变化,复杂度由原来的 o(n3) 到现在的 O(n)。了解 diff 的过程能更加高效的使用框架,或者遇到bug时可以往更加底层的方向上思考。

Virtual Dom

Virtual Dom 是什么

Vertial Dom 本质是一个 JS 对象,并且至少包含 tag(标签名), elemement(真实 Dom 对象), data(Dom 属性), children(孩子节点) 这几个属性,通过 Vertial Dom 我们可以描绘 Dom 树中各个元素的位置关系。 借助 Vertial DOM ,可以实现跨平台渲染,如 vue ssr ,而且当 DOM 节点改变时,会通过对比新 VD 和旧 VD 的变化,只操作变化的 DOM 节点,从而减少 DOM 操作次数,提高渲染效率。

Virtual Dom 如何实现

Vue 模板经过编译优化转换后生成一个 render 函数,通过调用 render 函数,可以生成一个实例的 Vertial Dom,每次 Mounted 或者 Update 时,都会调用这个 render 函数,生成新的 Vertial Dom,然后通过对比新旧 DOM,把不同的部分更新到真实 DOM 树中,一次完整的Vue渲染就完成了。一个 VNode 的基本组成部分:elm(真实 DOM 节点),tag(元素类型),text(文本节点才有),children(子界节点)

VNode = {
    elm: li,
    tag: "li",
    text: undefined,
    children: [{
        children: undefined
        elm: text
        tag: undefined
        text: "B"
    }]
}

Virtual Dom 转换成真实 Dom

主要是利用 document.createElement 的方法,递归 VNode。 以下是简化版的实现代码。

// 创建dom元素
function createElement(vdom) {
    // 如果vdom是字符串或者数字类型,则创建文本节点,比如“Hello World”
    if (typeof vdom === 'string' || typeof vdom === 'number') {
        return doc.createTextNode(vdom);
    }

    const {tag, props, children} = vdom;

    // 1. 创建元素
    const element = doc.createElement(tag);

    // 2. 属性赋值
    setProps(element, props);

    // 3. 创建子元素
    // appendChild在执行的时候,会检查当前的this是不是dom对象,因此要bind一下
    children.map(createElement)
            .forEach(element.appendChild.bind(element));

    return element;
}

// 属性赋值
function setProps(element, props) {
    for (let key in props) {
        element.setAttribute(key, props[key]);
    }
}

分析 Diff

刚刚已经说过了,组件数据变化后,组件更新,调用 render 方法生成新的 VNode 节点,然后通过 Dom Diff 算法把不同的地方渲染到视图上。diff 比较只会在同层级上经行,不会跨级比较,如图。

源码分析

patch

diff 的过程就是调用 patch,当两个节点有价值去比较时,就调用 patchVnode 把不同的地方映射到真实 dom 中。

function patch (oldVnode, vnode, hydrating, removeOnly, parentElm, refElm) {
    if (isUndef(oldVnode)) {
      // 第一次渲染时就直接创建新节点
      isInitialPatch = true;
      createElm(vnode, insertedVnodeQueue, parentElm, refElm);
    } else {
      if (sameVnode(oldVnode, vnode)) {
        // 两个 dom 是有价值比较时,则打补丁
        patchVnode(oldVnode, vnode, insertedVnodeQueue, removeOnly);
      } else {
        // 没有价值比较时,则直接用新节点替换旧节点
        var oldElm = oldVnode.elm;
        createElm(vnode);
      }
    }
    return vnode.elm
  } 

sameVnode 函数就是看这两个节点是否值得比较,当标签相同,key 相同,如果是 input 时,type 要相同,且 data 是同一个对象时,才值得比较。

function sameVnode (a, b) {
  return (
    a.key === b.key &&
    a.tag === b.tag &&
    a.isComment === b.isComment &&
    isDef(a.data) === isDef(b.data) &&
    sameInputType(a, b)
  )
}

patchVnode

如果不值得比较,则直接创建新节点插入到文档中,若值得比较,则调用 patchVNode 打补丁。

  function patchVnode (oldVnode, vnode, insertedVnodeQueue, removeOnly) {
    if (oldVnode === vnode) {
      return
    }

    var elm = vnode.elm = oldVnode.elm;
    var oldCh = oldVnode.children;
    var ch = vnode.children;

    if (isUndef(vnode.text)) {
      // 如果新节点不是文本
      if (isDef(oldCh) && isDef(ch)) {
        // 如果子节点不相同,则更新子节点
        if (oldCh !== ch) { updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly); }
      } else if (isDef(ch)) {
        // 如果旧节点没有子节点,新节点有子节点,则新建子节点插入
        if (isDef(oldVnode.text)) { nodeOps.setTextContent(elm, ''); }
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
      } else if (isDef(oldCh)) {
        // 如果新节点没有孩子节点,旧节点有孩子节点,则删除旧节点
        removeVnodes(elm, oldCh, 0, oldCh.length - 1);
      } else if (isDef(oldVnode.text)) {
        // 如果旧节点是文本,新节点不是文本,且没有孩子,且设置文本为空
        nodeOps.setTextContent(elm, '');
      }
    } else if (oldVnode.text !== vnode.text) {
      // 如果新节点是文本,且跟旧文本不一致,则直接插入新节点的文本
      nodeOps.setTextContent(elm, vnode.text);
    }
  }

const el = vnode.el = oldVnode.==el 这是很重要的一步,让vnode.el引用到现在的真实dom,当el修改时,vnode.el会同步变化。

节点的比较有5种情况

  1. oldNode === vnode,两个节点完全一样就没必要比较。
  2. 如果都是文本节点,文本内容不同时,直接改变文本内容
  3. 如果都有子节点且不相同时,则调用 updateChildren 更新子节点
  4. 如果旧节点没有子节点,新节点有子节点,则新建新子节点插入
  5. 如果新节点没有孩子节点,旧节点有孩子节点,则删除旧子节点

updateChildren

function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
   var oldStartIdx = 0;
   var newStartIdx = 0;
   var oldEndIdx = oldCh.length - 1;
   var oldStartVnode = oldCh[0];
   var oldEndVnode = oldCh[oldEndIdx];
   var newEndIdx = newCh.length - 1;
   var newStartVnode = newCh[0];
   var newEndVnode = newCh[newEndIdx];
   var oldKeyToIdx, idxInOld, elmToMove, refElm;

   // 当两个数组都还没到底时,则继续比较。
   while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
     if (isUndef(oldStartVnode)) {
       // 如果旧开始节点不存在,则找下一个。有可能是外部的 dom 不是用 vue 控制,vue 这里做保护
       oldStartVnode = oldCh[++oldStartIdx]; // Vnode has been moved left
     } else if (isUndef(oldEndVnode)) {
       // 如果旧结束节点不存在,则找下一个
       oldEndVnode = oldCh[--oldEndIdx];
     } else if (sameVnode(oldStartVnode, newStartVnode)) {
       // 如果旧的首个子节点和新的首个子节点相同,则再递归对比这个子节点,且不需要交换位置
       patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
       oldStartVnode = oldCh[++oldStartIdx];
       newStartVnode = newCh[++newStartIdx];
     } else if (sameVnode(oldEndVnode, newEndVnode)) {
       // 如果旧的尾巴和新的尾巴相同,则再递归对比这个子节点,且不需要交换位置
       patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
       oldEndVnode = oldCh[--oldEndIdx];
       newEndVnode = newCh[--newEndIdx];
     } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
       // 如果旧的开始节点和新的结束节点一致,则以旧的节点替换新的节点,且交换位置,把旧的开始节点移动到旧的结束节点后面
       patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
       canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm));
       oldStartVnode = oldCh[++oldStartIdx];
       newEndVnode = newCh[--newEndIdx];
     } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
       // 如果旧的结束节点和新的开始节点一样,则给旧的节点打补丁,然后把旧的结点移动到最前
       patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
       canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
       oldEndVnode = oldCh[--oldEndIdx];
       newStartVnode = newCh[++newStartIdx];
     } else {
       // 如果几种情况都不符合,则通过 key 找到旧的 dom 节点
       if (isUndef(oldKeyToIdx)) { oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx); }
       idxInOld = isDef(newStartVnode.key) ? oldKeyToIdx[newStartVnode.key] : null;
       if (isUndef(idxInOld)) { // New element
         // 如果找不到,则创建新节点
         createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm);
         newStartVnode = newCh[++newStartIdx];
       } else {
         elmToMove = oldCh[idxInOld];
         if (sameVnode(elmToMove, newStartVnode)) {
           // 如果找到了,且是值得比较的,则继续打补丁
           patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
           oldCh[idxInOld] = undefined;
           // 补丁打完后,则把旧节点移动到正确的位置
           canMove && nodeOps.insertBefore(parentElm, newStartVnode.elm, oldStartVnode.elm);
           newStartVnode = newCh[++newStartIdx];
         } else {
           // 如果只是 key 一样,但 tag 或者其他改变了,则创建新的节点插入
           createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm);
           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(parentElm, oldCh, oldStartIdx, oldEndIdx);
   }
 }

我们看看 diff 算法是怎么移动旧节点变成新节点,新旧节点如下图。

首先会记录这几个变量,然后开始同时遍历新旧节点。当两个子节点都还没到底的时候,会继续比较,如果其中一个到底了,则跳出循环。

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx){ … }

这个遍历里主要的几个分支

  1. 前两个分支,isUndef(oldStartVnode) 和 isUndef(oldEndVnode) 是保护,确保找到开始和结束节点。
  2. 如果旧的头部和新的头部相等,则不移动 dom 位置,移动 newStartIdx++ 和 oldStartIdx++。
  3. 如果旧的尾部和新的尾部相等,则不移动 dom 位置,移动 newEndIdx-- 和 oldEndIdx–。
  4. 如果旧的头部和新的尾部相等,则把旧的头部移动到最后,移动 oldStartIdx++ 和 newEndIdx–。
  5. 如果旧的尾部和新的头部相等,则把旧的尾部移到最前,移动 oldEndIdx-- 和 newStartIdx++。
  6. 如果以上几种情况都不符合,则通过 key 找旧节点的 idx,如果找到了,继续打补丁,打完补丁后,则把节点移动到 newStartNode前面 的位置上。如果找不到,则创建新的节点,移动到 newStartNode 的前面。移动 newStartIdx++。


以上遍历跳出后,判断哪个子节点数组先到底。

  1. 如果新子节点数组先到底,旧的还没到底,则删除旧的多余节点。
  2. 如果旧的子数组线到底,则新增新的子节点。

例子

总结

  1. 列表使用Key,可以最大化利用节点,另外不容易出bug。
  2. 尽量不要跨层级操作,比如新节点都是同样的节点,但是父节点改变了,此时 vue 暂时没有优化这种情况,目前只比较同层级,用 insertBefault 操作。
  3. 尽量自己手工优化 dom,简化 dom 结构,不需要的数据不要绑定到模板上。
最后一次编辑于  11-25  
点赞 0
收藏
评论