vue2-diff算法

1、diff算法是什么？
diff算法是一种通过同层的树节点进行比较的高效算法。
其有两个特点：
比较只会在同层级进行，不会跨层级进行。
在diff比较的过程中，循环从两边向中间比较。
diff算法在很多场景中都有应用，在vue中，作用于虚拟Dom渲染成真实dom的新旧Vnode节点比较

2、比较方式
diff整体策略为：深度优先，同层比较
1）比较只会在同层级进行，不会跨层级比较

2）比较的过程中，循环从两边向中间收拢。

下面举一个vue通过diff算法更新的例子。
新旧vnode节点如下图所示：

第一次循环后，发现旧节点D与新节点D相同，直接复用旧节点D作为diff后的第一个真实节点，同时旧节点endIndex移动到C，新节点的startIndex移动到C。
第二次循环后，同样是旧节点的末尾和新节点的开头相同（节点C），同理，diff后创建了C的真实节点插入到第一次创建的D节点后面，同时旧节点的endIndex移动到了B，新节点的startIndex移动到了E。

第三次循环中，发现E没有找到，这时候只能直接创建新的真实节点E，插入到第二次创建的C节点之后。同时新节点的startIndex移动到了A,旧节点的startIndex和endIndex都保持不动。

第四次循环中，发现了新旧节点的开头相同（都是A），于是diff后创建了A的真实节点，插入到前一次创建的E节点后面。同时旧节点的startIndex移动到了B，新节点的startIndex移动到了B。

第五次循环中，与第四次循环一样，因此diff后创建了B真实节点，插入到前一次创建的A节点后面。同时旧节点的startIndex移动到了C，新节点的startIndex移动到了F。

新节点的startIndex已经大于endIndex了，需要创建newStartIdx和newEndIdx之间的所有节点，也就是节点F，直接创建节点F对应的真实节点放到B节点后面。

3、原理分析
当数据发生改变时，set方法会调用Dep.notify通知所有订阅者Watcher，订阅者就会调用patch给真实的DOM打补丁，更新相应的视图。
源码位置：/src/core/vdom/patch.js


patch函数前两个参数位为oldVnode和Vnode，分别代表新的节点和之前旧的节点，主要是做了4个判断。
没有新节点，直接触发旧节点的destory钩子
没有旧节点，说明是页面刚开始初始化的时候，此时根本不需要比较，直接全是新建，所以调用createElm
旧节点和新节点自身一样，通过saveVnode判断节点是否一样，一样时直接调用patchVndoe去处理这两个节点
旧节点和新节点自身不一样，当两个节点不一样时，直接创建新节点，删除旧节点。

下面分析下patchVnode部分：




patchVnode主要做了以下几个判断：
新节点是否为文本节点，如果是，则直接更新dom的文本内容为新节点的文本内容
新节点和旧节点如果都有子节点，则处理比较更新子节点
只有新节点有子节点，旧节点没有，那就不用比较了，所有节点都是全新的，所以直接全部新建就好了，新建是指创建出所有新的DOM,并且添加进父节点
只有旧节点有子节点，新节点没有，说明更新后的页面，旧节点全部都不见了，那么要做的就是把所有旧节点删除，也就是直接把DOM删除

子节点不完全一致，则调用updateChildren





while主要是处理了以下5个场景：
当新老Vnode节点的start相同时，直接patchVndoe，同时新老Vnode节点的开始所以都加1
当新老Vnode节点的end相同时，同样直接patchVnode，同时新老Vnode节点的结束所以都减1
当老节点Vndoe的start和新Vnode节点的end相同时，这时候patchVndoe后，还需要将当前真实dom节点移动到oldEndVnode的后面，同时老Vnode节点开始索引加1，新Vnode节点的结束所以减1
当老Vnode节点的end和新Vnode节点的start相同时，这时候patchVnode后，还需要将当前真实dom节点移动到oldStartVnode的前面，同时老Vnode节点结束索引减1，新Vnode节点的开始索引加1
如果都不满足上述4种情况，那说明没有相同的节点可以复用，则会分为以下两种情况。
从旧的Vnode为key的值，对应index序列为value值的哈希表中找到与newStartVnode一致key的旧的Vnode节点，再进行patchVndoe，同时将这个真实dom移动到oldStartVnode对应的真实dom的前面
调用createElm创建一个新的Dom节点放到当前newStartIdx的位置。

4、小结
当数据发生改变时，订阅者watcher就会调用patch给真实的dom打补丁
通过isSameVNode进行判断，相同则调用patchVnode方法

patchVnode做了以下操作：
找到对应的真实dom，称为el
如果都有文本节点且不相等，将el文本节点设置为Vnode的文本节点
如果oldVnode有子节点而Vnode没有，则删除el子节点
如果oldVnode没有子节点而Vnode有，则将Vnode的子节点真实化后添加到el
如果两者都有子节点，则执行updateChildren函数比较子节点

updateChildren主要进行以下操作：
设置新旧Vnode的头尾指针
新旧头尾指针进行比较，循环向中间靠拢，根据情况调用patchVnode进行patch重复流程，调用createElem创建一个新节点，从哈希表寻找key一致的Vnode节点再分情况操作。