snabbdom 介绍

Snabbdom 是一个虚拟 DOM 库，专注提供简单、模块性的体验，以及强大的功能和性能。由于vue2.x中的diff借鉴了snabbdom。所以我们在这篇文章以snabbdom的源码为研究对象。
snabbdom github链接

• 优异的性能，在 Virtual DOM Benchmark 测试中，Snabbdom 是最快的虚拟 DOM 库之一
• 可通过模块进行扩展

（我的废话）由于snabbdom在v0.6.0版本以上是用TypeScript写的，那么我们主要也是以TypeScript版本的去进行理解。TypeScript编写的库对于我们进行源码解读是有好处的，虽然看起来会多很多类型判断，但是同时也增加了代码可读性，例如在库中的v-node会有很多的参数，如下

export function vnode (sel: string | undefined,
  data: any | undefined,
  children: Array<VNode | string> | undefined,
  text: string | undefined,
  elm: Element | Text | undefined): VNode {
  const key = data === undefined ? undefined : data.key
  return { sel, data, children, text, elm, key }
}
复制代码

那么我们就可以很轻易的得到Vnode中每个参数代表是什么，所以在下面的内容，我们也会以Vnode为切入点去理解snabbdom的主要功能

虚拟DOM 、虚拟节点(Vnode)

虚拟DOM:用JavaScript对象描述DOM的层次结构。DOM中的一切属性都在虚拟DOM中有对应的属性

至于如何将DOM转换成虚拟DOM可以参考我上一次的分享，类似于这篇笔记中将DOM转化为tokens的过程，感兴趣可以自己看一下我就不再介绍了。 mustache模板引擎链接

在snabbdom中，作者用了一个h函数对我们的虚拟DOM进行了简单的处理，将我们的不规则的虚拟DOM封装成了各种参数都有对应位置的Vnode虚拟节点。让我们再来看一看源码中的Vnode

export function vnode (sel: string | undefined,
  data: any | undefined,
  children: Array<VNode | string> | undefined,
  text: string | undefined,
  elm: Element | Text | undefined): VNode {
  const key = data === undefined ? undefined : data.key
  return { sel, data, children, text, elm, key }
}
复制代码

我来简单讲一下Vnode中每个参数的意思

1. sel:DOM中的各个标签如”div”,”p”,”h1″,”a”等等
2. data:标签上的属性以及样式，如a标签中的链接，class之类的
3. children:这个DOM上的子节点
4. text:文本内容
5. elm:挂载的标签
6. key:服务于最小更新(diff)后面会讲

h函数

那么h函数做了什么事情呢,让我们来先看一下h函数中的核心部分

export function h (sel: string): VNode
export function h (sel: string, data: VNodeData | null): VNode
export function h (sel: string, children: VNodeChildren): VNode
export function h (sel: string, data: VNodeData | null, children: VNodeChildren): VNode
export function h (sel: any, b?: any, c?: any): VNode {
 var data: VNodeData = {}
 var children: any
 var text: any
 var i: number
 if (c !== undefined) {
   if (b !== null) {
     data = b
   }
   if (is.array(c)) {
     children = c
   } else if (is.primitive(c)) {
     text = c
   } else if (c && c.sel) {
     children = [c]
   }
 } else if (b !== undefined && b !== null) {
   if (is.array(b)) {
     children = b
   } else if (is.primitive(b)) {
     text = b
   } else if (b && b.sel) {
     children = [b]
   } else { data = b }
 }
 if (children !== undefined) {
   for (i = 0; i < children.length; ++i) {
     if (is.primitive(children[i])) children[i] = vnode(undefined, undefined, undefined, children[i], undefined)
   }
 }
 if (
   sel[0] === 's' && sel[1] === 'v' && sel[2] === 'g' &&
   (sel.length === 3 || sel[3] === '.' || sel[3] === '#')
 ) {
   addNS(data, children, sel)
 }
 return vnode(sel, data, children, text, undefined)
};

复制代码

在h函数中，我们可以看到对a、b、c做了各种各样的if判断，实际上就是判断这个虚拟DOM中，少了哪些参数。让传入的参数能到对应的位置。

在这里我从snabbdom中的引入了h函数，将下面的虚拟DOM转换成Vnode辅助理解


当我们拿到了我们想要的Vnode，不考虑其他的边边角角的功能（识别style 、class之类的功能），接下来我们只需要做两件事了

1. 利用diff算法. 让我们知道oldVnode（旧的节点）和newVnode（新的节点）之间的不同。
2. 知道不同之后然后将旧的节点最小量更新为新的节点，也就是把不同的虚拟DOM渲染到真实的DOM中去。

diff算法

diff简介

这里我们介绍一下diff，新虚拟DOM和老虚拟DOM进行diff（精细化比较），算出应该如何最小量更新，最后反应到真正的DOM上。让我们来看一下下面这张diff的源码图（snabbdom的inis.ts中的updateChildren函数）。先不用关注里面的具体内容

我们可以先通过简单的观察发现，在不停的if判断中穿插着patchVnode。patchVnode()简单的讲就是更新节点的办法。那么在这个过程中，我们通过不断比较，找到不同的地方，然后针对性的更新节点。

好的，到这里我们就可以开始diff了。但是在下面的学习过程中同时我们要带着两个问题

1. diff到底是怎么找到新旧Vnode中不同的地方，并更新旧节点。
2. 找到了之后是如何上树

diff算法的过程

这里偷了React’s diff algorithm中的图来介绍

图中连线的都是同一层级的节点，我们在diff的原则就是。只进行同层比较，不会进行跨层比较。即使是同一片虚拟节点，但是跨层了，就不会diff了，会删除旧的，插入新的。

关于key

在同一层级节点中，只有是同一个虚拟节点，才进行精细化，否则就是暴力删除旧的插入新的。那么如何确定我们的节点是同一个虚拟节点呢？答案是添加唯一标识key。当我们为每一个节点都添加了唯一的key，我们再去更新就会比较有效率了。

当节点z想插入cd之间的节点时

无key更新

如果节点没有添加key，那么z就会硬生生的挤入cd之间然后把d的位置占住。那么后面的更新就会把d变成z，e变成d,然后再重新创建一个e。如果后面还有fghizklmnopgrszuvwhyz的话，那么后面每一个节点都需要重新更新。也就是一个个vnode去进行比较，发现其文本节点不对，就会一个个进行替换例。那么我们怎么来进行优化呢

有key更新

再次偷图React’s diff algorithm

当我们为每一个节点都添加上了key，再次在cd之间插入z，c后面的节点在更新的时候就不会，重新创建了。换个方式说，c后面的节点是复用了，并没有更新。那么这样的效率就会快很多了，只需要在c后面创建一个z就可以了

对比了一下着这个案例的两种情况，我们可以发现携带key的时候，我们可以把没有变化的部分识别出来，再添加的时候就只做了一次添加的DOM操作。而没有key的时候，那么我们需要做的DOM操作次数就得看这个节点后面有多长了……

patch函数

patch函数是我们做diff的一个入口，我们将从这个函数为起点，一步一步的得到我们想要的效果。在snabbdom中的init.ts的最后，返回了一个patch函数。我会在源码上添加注释，来解释一些关键的判断，帮助理解。如下

return function patch(oldVnode: VNode | Element, vnode: VNode): VNode {
   //这里oldVnode的类型是VNode或者Element也就说明了我们的oldVnode可以传一个DOM元素。
   let i: number, elm: Node, parent: Node
   const insertedVnodeQueue: VNodeQueue = []
   for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]()
   // 判断oldVnode是虚拟节点还是DOM节点
   if (!isVnode(oldVnode)) {
     //如果oldVnode不是虚拟节点，那么将oldVnode通过emptyNodeAt()包装成虚拟节点
     oldVnode = emptyNodeAt(oldVnode)
   }
   //通过sameVnode()判断oldVnode和我们传入的新的Vnode是不是同一个节点
   if (sameVnode(oldVnode, vnode)) {
     //如果是，那就进行精细化比较
     patchVnode(oldVnode, vnode, insertedVnodeQueue)
   } else {
     //不是就之间删除旧的节点、插入新的节点
     elm = oldVnode.elm!
     parent = api.parentNode(elm) as Node
	 //创建新的节点
     createElm(vnode, insertedVnodeQueue)

     if (parent !== null) {
       api.insertBefore(parent, vnode.elm!, api.nextSibling(elm))
       //删除旧的节点
       removeVnodes(parent, [oldVnode], 0, 0)
     }
   }

   for (i = 0; i < insertedVnodeQueue.length; ++i) {
     insertedVnodeQueue[i].data!.hook!.insert!(insertedVnodeQueue[i])
   }
   for (i = 0; i < cbs.post.length; ++i) cbs.post[i]()
   return vnode
 }
}
复制代码

在这里有必要稍微的说一下，将vnode转换为DOM我们使用了createElm()函数。但由于我们传入的Vnode是有子节点Children的，那么我们在创建节点的时候就会遇到数组对象嵌套的问题。在这里我就不具体细节的将createElm进行解读。但比较主要的是，createElm()在前面写好了vnode的各个属性该去的地方，然后再通过在对子节点遍历的时候调用自己，也就是递归来解决这个问题的，这里我用查找功能标出了createElm这个函数，方便大家阅读，我也将图贴在下面。

同时我也将sameVnode()函数的代码贴下来，贴出来的原因是让大家看到snabbdom对个两个Vnode是不是相同的判断依据

1. vnode的key相同
2. vnode的选择器相同

function sameVnode(vnode1: VNode, vnode2: VNode): boolean {
  return vnode1.key === vnode2.key && vnode1.sel === vnode2.sel
}
复制代码

其他的小函数也确实不难，感兴趣的就自己理解，我们主要先把大体逻辑理通，主要是我懒( ̀⌄ ́)

回到正题，通过patch函数我们可以看到，当我们进行了两次判断后，进入了patchVnode函数，那么接下来我们顺藤摸瓜进入patchVnode函数看看

patchVnode函数

patchVnodez主要就是告诉了我们虚拟 DOM 如何实现 DOM 的更新，做了哪些逻辑了判断。在学习这一部分的时候，需要思考为什么可以这样判断？为什么要这样做？

function patchVnode(oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) {
    const hook = vnode.data?.hook
    hook?.prepatch?.(oldVnode, vnode)
    const elm = vnode.elm = oldVnode.elm!
    //定义旧节点的子节点
    const oldCh = oldVnode.children as VNode[]
    //定义新节点的子节点
    const ch = vnode.children as VNode[]
    //判断oldVnode和vnode是不是同一个对象
    if (oldVnode === vnode) return // 是，就不做操作

    if (vnode.data !== undefined) {
      for (let i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
      vnode.data.hook?.update?.(oldVnode, vnode)
    }
    //判断vnode中是否有text属性，isUndef是判断里面的内容是不是undefined
    if (isUndef(vnode.text)) {
      //如果vnode.text是undefined
      //当vnode中没有text属性，就意味着vnode中存在children

      //如果oldCh和ch都不是undefined
      if (isDef(oldCh) && isDef(ch)) {
        //并且oldCh不等于ch，进入updateChildren()
        if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue)
      } else if (isDef(ch)) {
        //如果Vnode有Children
        //添加Vnode中的Children
        if (isDef(oldVnode.text)) api.setTextContent(elm, '')
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
      } else if (isDef(oldCh)) {
        //如果oldVnode有Children
        //删除oldVnode中的Children
        removeVnodes(elm, oldCh, 0, oldCh.length - 1)
      } else if (isDef(oldVnode.text)) {
        api.setTextContent(elm, '')
      }
      //判断oldVnode和vnode的text是否相同
    } else if (oldVnode.text !== vnode.text) {
      //判断oldCh是否存在
      if (isDef(oldCh)) {
        //如果存在，旧把oldCh删除，然后吧vnode.text替换进去
        removeVnodes(elm, oldCh, 0, oldCh.length - 1)
      }
      api.setTextContent(elm, vnode.text!)
    }
    hook?.postpatch?.(oldVnode, vnode)
  }
复制代码

到这里我们可以看到虽然我们是说提高性能，但是还是有些地方是直接删除旧的插入新的。原因可能是这种情况其实我们并不会经常遇到，所以在优化的过程中并不一定要全都去做对比。接下来我们要进入最核心的部分updateChildren函数，也就是做diff算法地方。

updateChildren函数（diff算法）

patchVnode于updateChildren直接有一个互相引用的过程，因为我们第一次从patchVnode进入到updateChildren时，并不知道oldVnodeChildren中还有没有子节点，所以我们需要在每一次对比的中间再次加入patchVnode，这样循环调用，就可以对每一层有子节点的子节点都进行相应的处理

insertBefore在参考节点之前插入一个拥有指定父节点的子节点
首先我先将updateChildren函数代码贴出，然后分段讲解

function updateChildren(parentElm: Node,
    oldCh: VNode[],
    newCh: VNode[],
    insertedVnodeQueue: VNodeQueue) {
    let oldStartIdx = 0
    let 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: KeyToIndexMap | undefined
    let idxInOld: number
    let elmToMove: VNode
    let before: any

    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (oldStartVnode == null) {
        oldStartVnode = oldCh[++oldStartIdx] // Vnode might have been moved left
      } 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, 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)
        api.insertBefore(parentElm, oldStartVnode.elm!, api.nextSibling(oldEndVnode.elm!))
        oldStartVnode = oldCh[++oldStartIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
        api.insertBefore(parentElm, oldEndVnode.elm!, oldStartVnode.elm!)
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
      } else {
        if (oldKeyToIdx === undefined) {
          oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
        }
        idxInOld = oldKeyToIdx[newStartVnode.key as string]
        if (isUndef(idxInOld)) { // New element
          api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm!)
        } else {
          elmToMove = oldCh[idxInOld]
          if (elmToMove.sel !== newStartVnode.sel) {
            api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm!)
          } else {
            patchVnode(elmToMove, newStartVnode, insertedVnodeQueue)
            oldCh[idxInOld] = undefined as any
            api.insertBefore(parentElm, elmToMove.elm!, oldStartVnode.elm!)
          }
        }
        newStartVnode = newCh[++newStartIdx]
      }
    }
    if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
      if (oldStartIdx > oldEndIdx) {
        before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].elm
        addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
      } else {
        removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
      }
    }
  }
复制代码

diff分别在新旧的子节点的两头设置了指针，也就是四个指针。我们分别记录了这四个指针以及四个指针指向的Vnode

   let oldStartIdx = 0//指向旧节点的第一个Vnode
   let newStartIdx = 0//指向新节点的第一个Vnode
   let oldEndIdx = oldCh.length - 1//指向旧节点的最后一个Vnode
   let oldStartVnode = oldCh[0]//旧节点的第一个Vnode
   let oldEndVnode = oldCh[oldEndIdx]//旧节点的最后一个Vnode
   let newEndIdx = newCh.length - 1//指向新节点的最后一个Vnode
   let newStartVnode = newCh[0]//新节点的第一个Vnode
   let newEndVnode = newCh[newEndIdx]//新节点的最后一个Vnode
复制代码

在遍历过程中这四个指针都会向中间靠拢。
当oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx时结束循环

接下来要介绍着四个指针的具体移动规则

旧头(oldStartVnode) —-对比 —新头(newStartVnode)

这里简单说明一下，我们使用sameVnode()判断两个Vnode是否相同

1. 当新节点和老节点的第一个Vnode相同,即sameVnode(oldStartVnode, newStartVnode)，那么将该Vnode节点进行patchVnode。然后将oldStartIdx和newStartIdx两个指针+1，再将oldStartVnode和newStartVnode更新

     else if (sameVnode(oldStartVnode, newStartVnode)) {
       patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
       oldStartVnode = oldCh[++oldStartIdx]
       newStartVnode = newCh[++newStartIdx]
     } 
   复制代码

   过程如下图（自己画自己截的图，将就看叭QAQ）第一列是新节点newCh，第二列是老节点oldCh

旧尾(oldStartVnode) —对比 — 新尾(newStartVnode)

2. 当新节点和老节点的最后一个Vnode相同，即sameVnode(oldEndVnode, newEndVnode)，那么将该Vnode节点进行patchVnode。然后将oldEndIdx和newEndIdx两个指针-1，再将oldEndVnode和newEndVnode更新

	 else if (sameVnode(oldEndVnode, newEndVnode)) {
       patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
       oldEndVnode = oldCh[--oldEndIdx]
       newEndVnode = newCh[--newEndIdx]
     }
复制代码

旧头(oldStartVnode) —对比 —- 新尾(newStartVnode)

3. 当新节点的最后一个Vnode和老节点的第一个Vnode相同，即即sameVnode(oldStartVnode, newEndVnode)，那么将该Vnode节点进行patchVnode。然后将newEndIdx指针-1和oldStartIdx指针+1，然后把oldStartVnode移到oldEndVnode后面。

	else if (sameVnode(oldStartVnode, newEndVnode)) {
       patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
       api.insertBefore(parentElm, oldStartVnode.elm!, api.nextSibling(oldEndVnode.elm!))
       oldStartVnode = oldCh[++oldStartIdx]
       newEndVnode = newCh[--newEndIdx]
     }
复制代码

什么意思呢？就是当上面的新节点的D与旧节点的D通过sameVnode(oldStartVnode, newEndVnode)匹配上以后。为了将左边的旧节点变成右边的新节点，那么我们就将旧节点中的D移动到oldEndIdx指向的oldEndVnode的后面，也就是图中的B(注意是oldEndVnode的后面)。然后再将oldStartIdx指针+1和newEndIdx指针-1

在这里还要介绍一下insertBefore() 。在MDN中是这样介绍的：Node.insertBefore() 方法在参考节点之前插入一个拥有指定父节点的子节点。简单的说就是把一个节点添加到另一个节点的前面。而nextSibling()是一个节点的下一个节点。所以我们通过insertBefore() 配合nextSibling()，来把上面的D添加到B的下一个节点的前面。这样我们就把D加在B的后面了也就是这一行代码

api.insertBefore(parentElm, oldStartVnode.elm!, api.nextSibling(oldEndVnode.elm!))
复制代码

为什么不能用appendChild，是因为我们现在需要把节点添加到oldEndVnode的后面，而不是oldCh的后面。

旧尾(oldStartVnode) —-对比 — 新头(newStartVnode)

4. 当老节点的最后一个Vnode和老新节点的第一个Vnode相同，即sameVnode(oldEndVnode,newStartVnode)，那么将该Vnode节点进行patchVnode。然后将oldEndIdx指针-1和newStartIdx指针+1，然后把oldStartVnode移到oldEndVnode后面。

	else if (sameVnode(oldEndVnode, newStartVnode)) {
	    patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
	    api.insertBefore(parentElm, oldEndVnode.elm!, oldStartVnode.elm!)
	    oldEndVnode = oldCh[--oldEndIdx]
	    newStartVnode = newCh[++newStartIdx]
    }
复制代码

当oldEndVnode与newStartVnode匹配上之后呢，为了将左边的旧节点变成右边的新节点，那么我们就需要把D放到oldStartVnode也就是B的前面。然后再将oldEndIdx指针-1和newStartIdx指针+1。
将D放到B前面的方法也就是直接用刚刚介绍的insertBefore()方法

那么到这里，我以及将diff中的四种节点对比的方式讲清楚了（反正我觉得自己是讲清楚了，尽力了。自己在学习这部分源码的时候也是用PPT画了这个图，要是看着蒙圈就自己画画）。现在让我们再回来看这一段代码~

function updateChildren(parentElm: Node,
    oldCh: VNode[],
    newCh: VNode[],
    insertedVnodeQueue: VNodeQueue) {
    let oldStartIdx = 0//旧节点的起点指针
    let newStartIdx = 0//新节点的起点指针
    let oldEndIdx = oldCh.length - 1//旧节点最后一位指针
    let oldStartVnode = oldCh[0]//旧节点的起点指针指向的Vnode
    let oldEndVnode = oldCh[oldEndIdx]//旧节点的最后一位指针指向的Vnode
    let newEndIdx = newCh.length - 1//新节点最后一位指针
    let newStartVnode = newCh[0]//新节点的起点指针指向的Vnode
    let newEndVnode = newCh[newEndIdx]//新节点的最后一位指针指向的Vnode
    let oldKeyToIdx: KeyToIndexMap | undefined
    let idxInOld: number
    let elmToMove: VNode
    let before: any

    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (oldStartVnode == null) {
        oldStartVnode = oldCh[++oldStartIdx] // Vnode might have been moved left
      } 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)) {
      //旧头(oldStartVnode)  ----------对比 ---------- 新头(newStartVnode)
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
      //旧尾(oldStartVnode)  ----------对比 ---------- 新尾(newStartVnode)
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newEndVnode)) { 
      //旧头(oldStartVnode)  ----------对比 ---------- 新尾(newStartVnode)
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
        api.insertBefore(parentElm, oldStartVnode.elm!, api.nextSibling(oldEndVnode.elm!))
        oldStartVnode = oldCh[++oldStartIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldEndVnode, newStartVnode)) { 
      //旧尾(oldStartVnode)  ----------对比 ---------- 新头(newStartVnode)
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
        api.insertBefore(parentElm, oldEndVnode.elm!, oldStartVnode.elm!)
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
      } 
复制代码

前面四种都找不到

当新建节点的头尾四种对比都匹配不上时候,说明newStartVnode在oldCh中不在头尾或者并不存在。所以我们就用createKeyToOldIdx()方法制作了一个oldCh的映射的表。表中的值为每一个节点的key对应下标的值

else {
      if (oldKeyToIdx === undefined) {
        //创建oldCh的映射oldKeyToIdx
        oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
      }
      idxInOld = oldKeyToIdx[newStartVnode.key as string]
      if (isUndef(idxInOld)) { // New element
        //如果idxInOld是undefined，就创建一个newStartVnode放在oldStartVnode.elm前面
        api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm!)
      } else {
        //如果idxInOld不是undefined，那么就找出oldCh中含有idxInOld这一项记录为elmToMove
        elmToMove = oldCh[idxInOld]
        if (elmToMove.sel !== newStartVnode.sel) {
          //如果elmToMove和newStartVnode的标签(sel)不一样，那么我们还是要再创建一个newStartVnode放在oldStartVnode.elm前面
          api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm!)
        } else {
          //如果都一样就做一次patchVnode，效果在前文已经描述过，都差不多
          patchVnode(elmToMove, newStartVnode, insertedVnodeQueue)
          oldCh[idxInOld] = undefined as any
          //终于在oldCh中找到newStartVnode，然后更新到oldStartVnode的前面
          api.insertBefore(parentElm, elmToMove.elm!, oldStartVnode.elm!)
        }
      }
      newStartVnode = newCh[++newStartIdx]
    }
}
//创建oldKeyToIdx
function createKeyToOldIdx(children: VNode[], beginIdx: number, endIdx: number): KeyToIndexMap {
  const map: KeyToIndexMap = {}
  //以beginIdx为起点，endIdx为终点遍历每一项
  for (let i = beginIdx; i <= endIdx; ++i) {
    const key = children[i]?.key
    if (key !== undefined) {
      map[key] = i
    }
  }
  return map
}
复制代码

在前面四次if判断，跳过Vnode为null的节点(就这节点没有，看下一个节点)。进入四种sameVnode的判断以及一种例外情况。通过源码我们可以看到五种判断的顺序如下

1. 旧头(oldStartVnode) ———-对比 ———- 新头(newStartVnode)
2. 旧尾(oldStartVnode) ———-对比 ———- 新尾(newStartVnode)
3. 旧头(oldStartVnode) ———-对比 ———- 新尾(newStartVnode)
4. 旧尾(oldStartVnode) ———-对比 ———- 新头(newStartVnode)
5. 前面四种都找不到

至于为什么是这个顺序，可能是以各种情况出现的概率为考虑点吧~~

处理剩下节点

按照这个顺序循环完之后，我们会有三种情况

1. oldStartIdx > oldEndIdx。这种情况下就是老的Vnode节点遍历完了，但是新的Vnode节点还没有遍历完。所以这个时候新的Vnod比老的VNode节点多，所以我们需要将剩下的Vnode节点插入到真实的DOM节点中去。

if (oldStartIdx > oldEndIdx) {
  before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].elm
  addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
}
复制代码

遍历before相当于是一个标杆，标记了节点需要插入的地方
addNodes方法就是遍历newCh中多出来的部分，插入到before这个标杆前

function addVnodes(
    parentElm: Node,
    before: Node | null,
    vnodes: VNode[],
    startIdx: number,
    endIdx: number,
    insertedVnodeQueue: VNodeQueue
  ) {
 	 //遍历newCh中多出来的部分
    for (; startIdx <= endIdx; ++startIdx) {
      const ch = vnodes[startIdx]
      //只要节点不是null
      if (ch != null) {
      //插入到before这个标杆前
        api.insertBefore(parentElm, createElm(ch, insertedVnodeQueue), before)
      }
    }
  }
复制代码

放两张图把
before不为null：(ps:看了一下 github万星的vue源码讲解，那大佬把这个图画错了哈哈哈哈哈哈哈哈哈)但是人家画的好，这个看不懂就看他的叭大佬链接

before为null，当before为null时，在addVnode方法中的insertBefore会将后面的选中的节点自动排到队尾去

1. oldStartIdx <= oldEndIdx。这种情况下就是新的Vnode节点遍历完了，但是老的Vnode节点还没有遍历完。所以这个时候新的Vnod比老的VNode节点少，所以我们需要将老节点中多出来的Vnode节点删除。

removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
复制代码

2. newCh，oldCh刚好都遍历完，就那没事了，下班。

总结

到这里爷可算是给这玩意整完了,讲讲感受。

1. (我的绕口令)snabbdom的作者真厉害，能够构思出这中通过四个指针，来卡出新旧节点不同的地方，不知道为啥，我脑子总想着游标卡尺。指针就像两个外测量爪，外测量爪收缩的时候就像两个指针收缩，收缩到跳出while循环。内测量爪（外测量爪收缩到最小，内测量爪是会交叉的）或者外测量爪都卡着有意义的数据，就像4个节点一样。还有patchVnode和updateChildren的互相调用，除了解决了两个函数的本职工作，还通过互相调用解决了数组嵌套问题。与其相似的，createElm函数也通过递归去解决了这种数组嵌套的问题。
2. (我的废话)写博客确实很有助于我知识的沉淀。但是2W多字了，一个个画这些图，难顶……虽然vue源码中的diff和这区别不太大，函数名都差不多，但是vue3的diff好像更新了……但是收获还是很多，希望这些思想能像进击的巨人中的巨人死后随机传给下一个艾尔迪亚人一样传给我
3. 1点了，下班。有人看到问题就说一下，没人看就算了。