理解vue2.x之diff算法

了解diff算法前，应该先了解虚拟DOM(VNode)，在vue中是先创建VNode，再通过diff算法看哪个节点需要更新，最后批量处理，提高效率。

diff 算法本质

来看一段简单dom结构

<div id='app'>
   <span id='child'>1</span>
</div>

主要包含三个部分

自身的标签名（div）
自身的属性（id='app'）
子节点(span)

可以通过如下方式描述以上dom

const vnode = {
  tag:'div',
  attrs:{id:'app'},
  children:[{ tag:'span',attrs:{id:'child'},children:['1']}]
}

当用户对界面进行操作，比如把 div 的 id 改为 app2 ,将子节点 span 的文本子节点 1 改为 2,那么我们可以得到如下 vnode

const vnode2 = {
  tag:'div',
  attrs:{id:'app2'},
  children:[{ tag:'span',attrs:{id:'child'},children:['2']}]
}

那么我们运行 diff (vnode,vnode2),就能知道 vnode 和 vnode2 之间的差异如下：

div 的 id 改为 app2
span 的文本子节点 1 改为 2

diff算法的本质是找出两个对象之间的差异，目的是尽可能复用节点。

vue渲染过程

在vue框架中，我们写的html模板会被编译成渲染函数，渲染函数会生成vnode，最终以vnode渲染视图。

渲染流程如下：

1.png

若是首次渲染，此时并没有 oldVnode，直接以vnode为模板渲染视图。

若并非首次渲染，则对比vnode 与 oldVnode（上一次渲染的vnode）的差异，在现有的DOM上进行修改达到更新视图的效果。此过程称为patch，即打补丁。

Vue的复用机制

Vue的复用机制可以简单理解为：

Vue在对比vnode与oldVnode时, 会根据它们的key来判断它们是否指向同一个DOM，而这个key就是v-for语法中绑定的key属性。

如果key相同则会复用DOM，对原来DOM进行patch操作，使DOM内的具体内容与vnode一致。

例如：

// 当list发生变化时，由于key没有发生改变，渲染视图会复用之前的DOM节点
<div v-for="(item, index) in list" :key="index">
    ...
</div>
 
// 当list发生变化时，由于key发生改变，渲染视图不会复用之前的DOM节点,所有DOM节点会重新渲染
<div v-for="(item, index) in list" :key="item.id">
    ...
</div>

关于key的作用

官网推荐使用key，可理解为“使用唯一id作为key”。上面的例子中因为index作为key，和不带key的效果是一样的。index作为key时，每个列表项的index在变更前后也是一样的，都是直接判断为sameVnode然后复用。

说到底，key的作用就是更新组件时判断两个节点是否相同。相同就复用，不相同就删除旧的创建新的。

patch流程图

2.png

patch核心代码

patchVnode() {
    ...
    const oldCh = oldVnode.children
    const ch = vnode.children
    if (isUndef(vnode.text)) {
      if (isDef(oldCh) && isDef(ch)) { 
        // 子节点存在且不同时，执行updateChildren方法即diff算法，下文会详细讲解
        if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly) 
      } else if (isDef(ch)) {
        if (process.env.NODE_ENV !== 'production') {
          checkDuplicateKeys(ch)
        }
        if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
        // 渲染子节点并插入到DOM中
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
      } else if (isDef(oldCh)) {
        // 移除DOM下所有子节点
        removeVnodes(elm, oldCh, 0, oldCh.length - 1)
      } else if (isDef(oldVnode.text)) {
        // DOM文本置空
        nodeOps.setTextContent(elm, '')
      }
    } else if (oldVnode.text !== vnode.text) {
      // DOM文本设为vnode.text
      nodeOps.setTextContent(elm, vnode.text)
    }
    ...
}   
 
function isUndef (v) {
  return v === undefined || v === null
}
 
function isDef (v) {
  return v !== undefined && v !== null
}

当vnode与oldVnode都有子节点且子节点不相等时会调用updateChildren方法进行子节点之间的对比，也就是本文的重点diff算法。

diff过程

旧数组 [a,b,c,d]
新数组 [e,f,g,h]

怎么找出新旧数组之间的差异呢？我们约定以下名词 - 旧首（旧数组的第一个元素） - 旧尾（旧数组的最后一个元素） - 新首（新数组的第一个元素） - 新尾（新数组的最后一个元素）

一些工具函数

sameVnode--用于判断节点是否应该复用,这里做了一些简化，实际的diff算法复杂些，这里只用tag 和 key 相同，我们就复用节点，执行patchVnode，即对节点进行修改

function sameVnode(a, b) {
  return a.key === b.key && a.tag === b.tag
}

createKeyToOldIdx--建立key-index的索引,主要是替代遍历，提升性能

function createKeyToOldIdx(children, beginIdx, endIdx) {
  let i, key
  const map = {}
  for (i = beginIdx; i <= endIdx; ++i) {
    key = children[i].key
    if (isDef(key)) map[key] = i
  }
  return map
}

开始diff

旧首和新首对比

if (sameVnode(oldStartVnode, newStartVnode)) { 
      patchVnode(oldStartVnode.elm, oldStartVnode, newStartVnode);
      oldStartVnode = oldCh[++oldStartIdx];
      newStartVnode = newCh[++newStartIdx];
    }

旧尾和新尾对比

if (sameVnode(oldEndVnode, newEndVnode)) { //旧尾 和 新尾相同
      patchVnode(oldEndVnode.elm, oldEndVnode, newEndVnode);
      oldEndVnode = oldCh[--oldEndIdx];
      newEndVnode = newCh[--newEndIdx];
    }

旧首和新尾对比

if (sameVnode(oldStartVnode, newEndVnode)) { //旧首 和 新尾相同,将旧首移动到 最后面
      patchVnode(oldStartVnode.elm, oldStartVnode, newEndVnode);
      nodeOps.insertBefore(parentElm, oldStartVnode.elm, oldEndVnode.elm.nextSibling)
      oldStartVnode = oldCh[++oldStartIdx];
      newEndVnode = newCh[--newEndIdx];
    }

旧尾和新首对比,将旧尾移动到最前面

if (sameVnode(oldEndVnode, newStartVnode)) {//旧尾 和 新首相同 ,将 旧尾 移动到 最前面
      patchVnode(oldEndVnode.elm, oldEndVnode, newStartVnode);
      nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
    }

首尾对比都不符合 sameVnode 的话
尝试用 newCh 的第一项在 oldCh 内寻找 sameVnode,如果在 oldCh 不存在对应的 sameVnode ，则直接创建一个，存在的话则判断

符合 sameVnode，则移动 oldCh 对应的节点
不符合 sameVnode ,创建新节点

最后通过 oldStartIdx > oldEndIdx ，来判断 oldCh 和 newCh 哪一个先遍历完成

oldCh 先遍历完成,则证明 newCh 还有多余节点，需要新增这些节点
newCh 先遍历完成,则证明 oldCh 还有多余节点，需要删除这些节点

图解diff过程

4.png

（1）oldCh与newCh头指针指向的节点相同，newCh头指针、 oldCh头指针分别向前移一位。
（2）oldCh与newCh尾指针指向的节点相同，newCh头指针、 oldCh头指针分别向后退一位。

5.png

（3）newCh尾指针节点与oldCh头指针节点是同一个节点，将oldCh头指针对应的DOM插入到oldCh尾指针对应的DOM之后，newCh尾指针向后退一位，oldCh头指针向前移一位。

6.png

6-1.png

（4）oldCh头指针节点与newCh尾指针节点是同一个节点，将newCh尾指针对应的DOM插入到newCh头指针对应的DOM之前，oldCh头指针向前移一位，newCh尾指针向后退一位。

7.png

（5）newCh头指针节点与oldCh尾指针节点是同一个节点，将oldCh尾指针对应的DOM插入到oldCh头指针对应的DOM之前，newCh头指针向前移一位，oldCh尾指针向后退一位。

8.png

（6）newCh头指针节点在oldCh中没找到相同节点，直接以newCh头指针下的vnode为模板渲染DOM并插入到oldCh头指针对应的DOM之前，newCh头指针向前移一位。

9.png

10.png

（7）接下的节点3、4、5、6都满足头指针节点相同，只需将头指针向前移动，直至newCh头指针超过newCh尾指针，此时对比结束。

11.png

（8）oldCh剩下的未处理节点“8”视为需要移除的节点，将其从DOM中移除。

12.png

这时可以看到我们的DOM顺序已经与newCh顺序完全一致，diff结束。

diff核心代码

 
// 判断两个vnode是否相同
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)
      ) || (
        isTrue(a.isAsyncPlaceholder) &&
        a.asyncFactory === b.asyncFactory &&
        isUndef(b.asyncFactory.error)
      )
    )
  )
}
 
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, vnodeToMove, refElm;
 
    // removeOnly is a special flag used only by <transition-group>
    // to ensure removed elements stay in correct relative positions
    // during leaving transitions
    var canMove = !removeOnly;
 
    {
      checkDuplicateKeys(newCh);
    }
 
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (isUndef(oldStartVnode)) {
        oldStartVnode = oldCh[++oldStartIdx]; // Vnode has been moved left
      } else if (isUndef(oldEndVnode)) {
        oldEndVnode = oldCh[--oldEndIdx];
      } else if (sameVnode(oldStartVnode, newStartVnode)) {
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);
        oldStartVnode = oldCh[++oldStartIdx];
        newStartVnode = newCh[++newStartIdx];
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx);
        oldEndVnode = oldCh[--oldEndIdx];
        newEndVnode = newCh[--newEndIdx];
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx);
        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, newCh, newStartIdx);
        canMove && 
        nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
        oldEndVnode = oldCh[--oldEndIdx];
        newStartVnode = newCh[++newStartIdx];
      } else {
        if (isUndef(oldKeyToIdx)) { oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx); }
        idxInOld = isDef(newStartVnode.key)
          ? oldKeyToIdx[newStartVnode.key]
          : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);
        if (isUndef(idxInOld)) { // New element
          createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);
        } else {
          vnodeToMove = oldCh[idxInOld];
          if (sameVnode(vnodeToMove, newStartVnode)) {
            patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);
            oldCh[idxInOld] = undefined;
            canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm);
          } else {
            // same key but different element. treat as new element
            createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);
          }
        }
        newStartVnode = newCh[++newStartIdx];
      }
    }
    if (oldStartIdx > oldEndIdx) { // oldCh遍历结束，此时剩下的未处理的newCh则是新增节点
      refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm;
      addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);
    } else if (newStartIdx > newEndIdx) { // newCh遍历结束，此时剩下的未处理的oldCh则是需要移除的节点
      removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
    }
  }

dom渲染代码

在lifecycle.js中，它负责将Vnode转化为真实的dom，包含两个分支过程，dom的首次渲染，以及后续的dom的更新。

 Vue.prototype._update = function (vnode: VNode, hydrating?: boolean) {
    ...
    if (!prevVnode) {
      // initial render
      vm.$el = vm.__patch__(vm.$el, vnode, hydrating, false /* removeOnly */)
    } else {
      // updates
      vm.$el = vm.__patch__(prevVnode, vnode)
    }
    ...

vm.__ patch __(prevVnode, vnode)方法最终是在src/core/vdom/patch.js中定义，而这个方法是在createPatchFunction中返回的。

// src/core/vdom/patch.js
export function createPatchFunction (backend) {
  ……
  return function patch (oldVnode, vnode, hydrating, removeOnly, parentElm, refElm) {
    // 当前 VNode 未定义、老的 VNode 定义了，调用销毁钩子。
    if (isUndef(vnode)) {
      if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
      return
    }

    let isInitialPatch = false
    const insertedVnodeQueue = []

    if (isUndef(oldVnode)) {
      // 老的 VNode 未定义，初始化。
      isInitialPatch = true
      createElm(vnode, insertedVnodeQueue, parentElm, refElm)
    } else {
      // 当前 VNode 和老 VNode 都定义了，执行更新操作
      // DOM 的 nodeType http://www.w3school.com.cn/jsref/prop_node_nodetype.asp
      const isRealElement = isDef(oldVnode.nodeType) // 是否为真实 DOM 元素
      if (!isRealElement && sameVnode(oldVnode, vnode)) {
        // patch existing root node
        // 修改已有根节点
        patchVnode(oldVnode, vnode, insertedVnodeQueue, removeOnly)
      } else {
        // 已有真实 DOM 元素，处理 oldVnode
        if (isRealElement) {
          // 挂载一个真实元素，确认是否为服务器渲染环境或者是否可以执行成功的合并到真实 DOM 中
          if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) {
            oldVnode.removeAttribute(SSR_ATTR)
            hydrating = true
          }
          if (isTrue(hydrating)) {
            if (hydrate(oldVnode, vnode, insertedVnodeQueue)) {
              // 调用 insert 钩子
              // inserted：被绑定元素插入父节点时调用 
              invokeInsertHook(vnode, insertedVnodeQueue, true)
              return oldVnode
            }
          }
          // 不是服务器渲染或者合并到真实 DOM 失败，创建一个空节点替换原有节点
          oldVnode = emptyNodeAt(oldVnode)
        }

        // 替换已有元素
        const oldElm = oldVnode.elm
        const parentElm = nodeOps.parentNode(oldElm)

        // 创建新节点
        createElm(
          vnode,
          insertedVnodeQueue,
          oldElm._leaveCb ? null : parentElm,
          nodeOps.nextSibling(oldElm)
        )

        // 递归更新父级占位节点元素，
        if (isDef(vnode.parent)) {
          let ancestor = vnode.parent
          const patchable = isPatchable(vnode)
          while (ancestor) {
            for (let i = 0; i < cbs.destroy.length; ++i) {
              cbs.destroy[i](ancestor)
            }
            ancestor.elm = vnode.elm
            if (patchable) {
              for (let i = 0; i < cbs.create.length; ++i) {
                cbs.create[i](emptyNode, ancestor)
              }
              const insert = ancestor.data.hook.insert
              if (insert.merged) {
                for (let i = 1; i < insert.fns.length; i++) {
                  insert.fns[i]()
                }
              }
            } else {
              registerRef(ancestor)
            }
            ancestor = ancestor.parent
          }
        }

        // 销毁旧节点
        if (isDef(parentElm)) {
          removeVnodes(parentElm, [oldVnode], 0, 0)
        } else if (isDef(oldVnode.tag)) {
          invokeDestroyHook(oldVnode)
        }
      }
    }
    // 调用 insert 钩子
    invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch)
    return vnode.elm
  }
}

第一次传入patch方法是vm.$el是真实dom，直接在el元素上渲染页面，当数据更新触发渲染Watcher时会再次进入patch方法并带上当前的组件虚拟Dom(vm._vnode)，然后在patchVnode直接使用nodeOps操作dom元素，若有子级则使用updateChildren进行diff比对，比对时直接使用nodeOps操作dom(nodeOps.insertBefore)，在比较虚拟dom时，可以使用Vnode.elm属性得到真实dom并操作，待patch完成后再返回完整的elm给vm.el。

小结

diff 算法的本质是找出两个对象之间的差异
diff 算法的核心是子节点数组对比,思路是通过首尾两端对比
key 的作用主要是
决定节点是否可以复用
建立key-index的索引,主要是替代遍历，提升性能

参考：
https://blog.csdn.net/qq_36259513/article/details/103152653
https://zhuanlan.zhihu.com/p/76384873
https://segmentfault.com/a/1190000020716723