详解vue的diff算法原理

<div>
 <p>123</p>
</div>

var Vnode = {
 tag: 'div',
 children: [
  { tag: 'p', text: '123' }
 ]
};

<div>
 <p>123</p>
</div>

<div>
 <span>456</span>
</div>

function patch (oldVnode, vnode) {
 // some code
 if (sameVnode(oldVnode, vnode)) {
  patchVnode(oldVnode, vnode)
 } else {
  const oEl = oldVnode.el // 当前oldVnode对应的真实元素节点
  let parentEle = api.parentNode(oEl) // 父元素
  createEle(vnode) // 根据Vnode生成新元素
  if (parentEle !== null) {
   api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl)) // 将新元素添加进父元素
   api.removeChild(parentEle, oldVnode.el) // 移除以前的旧元素节点
   oldVnode = null
  }
 }
 // some code 
 return vnode
}

function sameVnode (a, b) {
 return (
 a.key === b.key && // key值
 a.tag === b.tag && // 标签名
 a.isComment === b.isComment && // 是否为注释节点
 // 是否都定义了data，data包含一些具体信息，例如onclick , style
 isDef(a.data) === isDef(b.data) && 
 sameInputType(a, b) // 当标签是<input>的时候，type必须相同
 )
}

patchVnode (oldVnode, vnode) {
 const el = vnode.el = oldVnode.el
 let i, oldCh = oldVnode.children, ch = vnode.children
 if (oldVnode === vnode) return
 if (oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text) {
  api.setTextContent(el, vnode.text)
 }else {
  updateEle(el, vnode, oldVnode)
  if (oldCh && ch && oldCh !== ch) {
   updateChildren(el, oldCh, ch)
  }else if (ch){
   createEle(vnode) //create el's children dom
  }else if (oldCh){
   api.removeChildren(el)
  }
 }
}

updateChildren (parentElm, oldCh, newCh) {
 let oldStartIdx = 0, newStartIdx = 0
 let oldEndIdx = oldCh.length - 1
 let oldStartVnode = oldCh[0]
 let oldEndVnode = oldCh[oldEndIdx]
 let newEndIdx = newCh.length - 1
 let newStartVnode = newCh[0]
 let newEndVnode = newCh[newEndIdx]
 let oldKeyToIdx
 let idxInOld
 let elmToMove
 let before
 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (oldStartVnode == null) { // 对于vnode.key的比较，会把oldVnode = null
   oldStartVnode = oldCh[++oldStartIdx] 
  }else if (oldEndVnode == null) {
   oldEndVnode = oldCh[--oldEndIdx]
  }else if (newStartVnode == null) {
   newStartVnode = newCh[++newStartIdx]
  }else if (newEndVnode == null) {
   newEndVnode = newCh[--newEndIdx]
  }else if (sameVnode(oldStartVnode, newStartVnode)) {
   patchVnode(oldStartVnode, newStartVnode)
   oldStartVnode = oldCh[++oldStartIdx]
   newStartVnode = newCh[++newStartIdx]
  }else if (sameVnode(oldEndVnode, newEndVnode)) {
   patchVnode(oldEndVnode, newEndVnode)
   oldEndVnode = oldCh[--oldEndIdx]
   newEndVnode = newCh[--newEndIdx]
  }else if (sameVnode(oldStartVnode, newEndVnode)) {
   patchVnode(oldStartVnode, newEndVnode)
   api.insertBefore(parentElm, oldStartVnode.el, api.nextSibling(oldEndVnode.el))
   oldStartVnode = oldCh[++oldStartIdx]
   newEndVnode = newCh[--newEndIdx]
  }else if (sameVnode(oldEndVnode, newStartVnode)) {
   patchVnode(oldEndVnode, newStartVnode)
   api.insertBefore(parentElm, oldEndVnode.el, oldStartVnode.el)
   oldEndVnode = oldCh[--oldEndIdx]
   newStartVnode = newCh[++newStartIdx]
  }else {
   // 使用key时的比较
   if (oldKeyToIdx === undefined) {
    oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) // 有key生成index表
   }
   idxInOld = oldKeyToIdx[newStartVnode.key]
   if (!idxInOld) {
    api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
    newStartVnode = newCh[++newStartIdx]
   }
   else {
    elmToMove = oldCh[idxInOld]
    if (elmToMove.sel !== newStartVnode.sel) {
     api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
    }else {
     patchVnode(elmToMove, newStartVnode)
     oldCh[idxInOld] = null
     api.insertBefore(parentElm, elmToMove.el, oldStartVnode.el)
    }
    newStartVnode = newCh[++newStartIdx]
   }
  }
 }
 if (oldStartIdx > oldEndIdx) {
  before = newCh[newEndIdx + 1] == null "text-align: center">

我们将它们取出来并分别用s和e指针指向它们的头child和尾child

现在分别对 oldS、oldE、S、E 两两做 sameVnode 比较，有四种比较方式，当其中两个能匹配上那么真实dom中的相应节点会移到Vnode相应的位置，这句话有点绕，打个比方

  
如果是oldS和E匹配上了，那么真实dom中的第一个节点会移到最后
  
如果是oldE和S匹配上了，那么真实dom中的最后一个节点会移到最前，匹配上的两个指针向中间移动
  
如果四种匹配没有一对是成功的，那么遍历 oldChild ， S 挨个和他们匹配，匹配成功就在真实dom中将成功的节点移到最前面，如果依旧没有成功的，那么将 S对应的节点 插入到dom中对应的 oldS 位置， oldS 和 S 指针向中间移动。

再配个图

第一步


oldS = a, oldE = d；
S = a, E = b;


oldS 和 S 匹配，则将dom中的a节点放到第一个，已经是第一个了就不管了，此时dom的位置为：a b d
第二步


oldS = b, oldE = d；
S = c, E = b;


oldS 和 E 匹配，就将原本的b节点移动到最后，因为 E 是最后一个节点，他们位置要一致，这就是上面说的： 当其中两个能匹配上那么真实dom中的相应节点会移到Vnode相应的位置 ，此时dom的位置为：a d b
第三步


oldS = d, oldE = d；
S = c, E = d;


oldE 和 E 匹配，位置不变此时dom的位置为：a d b
第四步


oldS++;
oldE--;
oldS > oldE;


遍历结束，说明 oldCh 先遍历完。就将剩余的 vCh 节点根据自己的的index插入到真实dom中去，此时dom位置为：a c d b
一次模拟完成。
这个匹配过程的结束有两个条件：
oldS > oldE 表示 oldCh 先遍历完，那么就将多余的 vCh 根据index添加到dom中去（如上图） S > E 表示vCh先遍历完，那么就在真实dom中将区间为 [oldS, oldE] 的多余节点删掉

下面再举一个例子，可以像上面那样自己试着模拟一下

当这些节点 sameVnode 成功后就会紧接着执行 patchVnode 了，可以看一下上面的代码


if (sameVnode(oldStartVnode, newStartVnode)) {
 patchVnode(oldStartVnode, newStartVnode)
}


就这样层层递归下去，直到将oldVnode和Vnode中的所有子节点比对完。也将dom的所有补丁都打好啦。那么现在再回过去看updateChildren的代码会不会容易很多呢？
总结


以上为diff算法的全部过程，放上一张文章开始就发过的总结图，可以试试看着这张图回忆一下diff的过程。



以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。