前言

该死的八股文，问就是diff。vue中使用两种diff方案，第一个是简单diff，用在vue2中，第二个是双端diff，vue3再用。首先明白diff要做什么，总的目的是为了能不动就不动，能移动绝不创建新的，实在没法才创建新的。 能不能就不动是指比如diff前的dom是 A B C D， diff后的dom是 B C D A，尽量只移走A, BCD不动。能移动绝不创建值得是将A移动到末尾而不是新创建一个A，

前提

1. sameVnode判断前后Vnode是否相同

function sameVnode(oldVnode, newVnode) {
    return (oldVnode.key === newVnode.key) && (
        oldVnode.tag === newVnode.tag &&
        oldVnode.isComment === newVnode.isComment &&
        isDef(oldVnode.data) === isDef(newVnode.data)
    )
}

2. patchVnode是将两个相同sameVnode的vnode处理，如果是普通的vnode，将新节点上属性移植到旧节点上，然后再对children递归进行diff。如果是组件节点。走组件的prepatch 流程。

简单diff

1. diff总是对同级的节点进行比较，如果节点不同，直接新节点替换旧节点
2. 如果节点相同，按照patchVnode方式，将新节点的属性复制到旧节点的dom上（复用了旧节点的dom避免创建新）
3. 再对children进行处理，按照头比较头，尾尾比较，新头比较旧尾，新尾比较旧头的方式循环处理
   1. 头头比较相同，头头指针++
   2. 尾尾相同，尾尾指针--，
   3. 新头旧尾相同，新头++。旧尾--。将旧尾的dom移动到旧头vnode对象的dom前面
   4. 新尾旧头相同，新尾--，旧头++。将旧头的dom移动到旧尾的下一个节点的前面。
   5. 将旧节点建立key-vnode的映射表，从新节点头到尾查找旧节点（通过key查找），没有key，直接双重循环找有没有和新节点相同的旧节点，找到相同的旧节点后，patchVnode节点，将旧节点移动到旧头dom前面，同时将旧节点的标志位设置为了null，在后续的查找中跳过该节点
   6. 如果没有在旧节点中查找到，证明该新节点是需要新创建
   7. 如果双端指针重合，证明复用已经完成，旧节点剩余的需要全部删除，新节点剩余的依次添加在新尾下一个节点的前面（反向循环队列）

其中可以看到关键的key，没有这个key，很多场景下都会走全部删除并新建的流程，

vue3的diff

1. 头头比较相同，尾尾也相同
2. 将旧建立索引表，新建一个数组表示新队列的在旧队列中索引（如果没有找到，置为0）
3. 找到这个数组的最长递增区块。
4. 将新节点从尾到头遍历，如果在最长递增区块中不处理（按照patchVnode流程走），如果是0，按照新建流程，插入当前vnode下一个vnode对应dom的前面。
5. 如果最后旧队列中还存在未处理的vnode，做删除操作。