题目：vue2.0源码——diff算法
一、diff概述
1.为什么vue需要diff算法
我们都知道vue的diff是为了更新DOM去服务的，那更新DOM是在什么样的场景下发生的呢？
想象一下，你的组件中一个状态发生改变了，按照我们之前讲的，会触发响应式数据的setter，一旦触发setter，就会调用相应watcher的get方法，这个get方法中会执行this.getter,而这个getter就是相应的渲染函数，这个渲染函数会生成一个全新的带有最新数据的虚拟DOM。
以上都是我之前文章的内容哦，如果不太熟悉，请看看之前的文章。
2.问题
如果生成了一个全新的DOM，我们可以有两种方式，一种是我们根据这个新的虚拟DOM，使用createEle()重新创建一个新的真实DOM，然后对之前的DOM，进行替换；另外一种方式是我们找到旧的虚拟DOM，和新的虚拟DOM之间的不同，然后只更新变化的那一部分。
相信不用我过多解释，我们都应该想到，vue肯定采取的第二种方式，因为如果每次状态的变化我们需要生成一个全新的DOM的话，那就会造成大量的不必要的，实际并未变化的DOM，从而造成大量的性能的浪费。
因为我们需要使用一种能够帮助我们找到新旧dom不同的算法，而这正是我们今天要仔细研究的算法。
3.找到位置
找到vue.js源码中的 __patch__方法。
因为从上一篇文章中，我介绍到了，每一次渲染watcher的使用都会调用一个getter，内部封装的是叫做 _update(_render() , vm)这个方法，而_update更新操作中伴随了一次__patch__，这个patch实际上就是diff新旧DOM并且真正更新DOM或创建DOM的过程。
小结：从这个过程中我们其实可以慢慢可以了解到vue其实在做框架设计的时候，都是分层去设计的，也就是说，编译是为了生成抽象语法树，它负责把字符串的模板构建成可操作的抽象语法树；而渲染函数是为了专门用来创建虚拟DOM的，并这个过程中保持获取最新值；然后diff算法做最终的拦截，帮助vue进行最小量的更新，大大节约vue对于性能的消耗。
可以看到我们的__patch__方法接受新旧两个虚拟DOM作为参数。
而__patch__实际上是这个patch方法。
patch方法是由createPatchFunction这个函数返回的，所以这个函数是个高阶函数，返回一个函数。接下来我们就来关注这个函数做了什么。
二、源码分析
diff算法的所有内容几乎都在函数函数里面。但这个函数实在是太大了有近一千多行，我用图把其中的结构画出来。
这个craetePatchFunction会接受一个参数backend，调用时会穿进去一个对象，这个对象中保存着所有的创建DOM的方法，供diff使用。
传进去的就是这个对象。
我们重点是看这两个函数。updateChildren，和patchVNode。就这么说吧，这两个函数就是diff函数的核心算法。
在返回回来的patch中，我们可以看到。他会首先做判空的处理，如果旧的虚拟DOM如果不存在，那么就根据新的虚拟DOM进行创建，这是为了使得第一次渲染DOM做的准备，因为第一次只有新的虚拟DOM，而没有旧的DOM，但diff存在的意义肯定是有虚拟DOM，因此我们可以直接看到后面，在进行后面的比较时，只有属于同一个节点，才会进行对于，如果不属于同一个节点，就直接进行暴力更新，这个diff的一个原则。想象一下如果新旧虚拟DOM的两个节点，如果根节点都发生了变化，那本质上diff会将整个新虚拟DOM进行重新渲染。
而判断两个虚拟DOM节点是否一样的标准就是下面这个函数。
至少要保证a节点的key和b节点的key是一样的，如果没有key的话，那么两个都是undefined也属于是相等的。asyncFactory在大多数情况下都是undefined，可以不用管，tag保持一样，data都有值，如果是input控件，在判断一样是否属于同一种类型的控件。只要保持这几个为true那么这个节点就属于同一个节点，就可以进行详细的diff而不用去重新创建。这个是合理的。接下来会进入patchVnode这个方法。
在这里我会使用断点测试一下！
在这里我们进入patchVnode方法进入看一下。
继续往下走
在这里vue做了一个优化的动作，就是虚拟DOM上的节点也分为静态节点和动态的节点，所谓静态节点就是那些永远不会发生变化的，没有任何指令操作，也没有绑定任何变量的节点，这样的节点在生成渲染函数的时候就会进行一个标记，所有标记了这些静态标记的点都会在这里判断，如果新旧虚拟DOM都是静态节点并且Key相同，就会直接返回，也就意味着这里的静态DOM并不会被更新，也不会执行下面的逻辑，从而达到优化性能的目的，因此我们再次验证的，所谓的diff本质上来讲其实最终一定是为了最小量更新。
在这里会对两个节点的属性进行同步，比如a和b节点他们的标签名一样，key也一样，可能某个属性不一样我们只需要让a的真实DOM节点依旧保持在页面上让后更新它的class , attrs , props , style等等就好了，这也就是为什么上面做same判断的时候就是只要data定义过就行，而不需要两个data完全保持一致，因此我们可以得出一个结论，那就是只要diff算法觉得不是一定需要替换DOM结构才能实现要求的话，diff就尽量不移除页面上的DOM，因为那太浪费性能了。
接下来就走到子节点了，diff本质上是一个递归的过程，这个updateChildren特别有意思我们可以一起来看一下。这里他会把新旧虚拟DOM的子元素都传过去。
这里的updateChildren方法会初始化定位一些元素，比如newStart , oldStart，newEnd，oldEnd。然后判断新的孩子中有没有重复的Key,还记得么，如果有重复的key，vue是会报警告的，因为那会影响vue在diff时的判断和效率。那为什么不对旧的虚拟DOM进行判断呢，因为上一次已经判断过了呀，上一次的新虚拟DOM不就是这一次的旧虚拟DOM么，要警告它早就有警告啦，好了不说这么多了，我们继续往下看核心的算法。
在这里算法当中可以说所有子元素的不同都可以被检测出来，首先检测newStart和oldStart如果两个属于相同的节点，摘取出来进行详细比较。再次检测newEnd 和 oldStartrt如果两个属于相同的节点，摘取出来进行详细比较，如果依然不同，在让newStart 和oldEnd进行比较。。。
我么可以画几张图来验证一下这个算法。
可以看一下加入我们这个时候是最常见的末尾插入，这个时候，每一次进行diff的时候，都会在newStart 和 oldStart这里停下，因为他们的节点是一样的，然后细细比较完毕之后，会将两个start都向前进一位，供下一次使用，一只到最后一个E和空比较发现不同，就走到最后一个条件重新创建一个节点，这样页面上就会多一个e节点了。
如果是在开头或者中间插入呢
同样的，每一次在进行循环的时候都会走到newEnd和oldEnd这里停下，然后进行详细对比发现没什么变化，然后将末尾索引前进一位。进而就会剩下最后一个E就和之前一样了，如果是插入中间的情况呢。
第一步他发现newStart和oldStart相同，然后停住了，索引前进一位，第二步他发现newStart和oldStart相同，然后停住了，索引前进一位，第三步，它发现newStart和oldStart不相同，但是oldEnd和newEnd相同于是又停住了，最后他发现又只剩下E了，然后创建了一个新的元素这个时候他是知道索引的，所以它知道把E插在哪里。而我们为什么需要key呢，其实我看过很多的博客，但是始终并未在源码层面给出依据，今天我将找到真正的依据。
依据就在这里，diff是根据这个函数来判断两个节点是否相似，其中就有对key的判断，在我上上图中，所谓A B C D就是key，大家想象一下加入没有这个所谓的Key的话，是不是在diff的过程中，即便两个节点的内容不同，那么这个sameVnode也会通过，在进行细细比较的时候，他发现实际上是不同的，又得需要创建新的节点了，但实际上是因为这个sameNode判断的太松了，导致没进入到正确的判断条件当中，但如果加上了这个key，在进行sameVnode判断的时候，就会因为A 和 E就是key不一样呀，所以会让条件继续判断从而一直进入到正确的判断中去。从而避免了误判导致的误创建。而这就是答案。
好了因此通过这样的递归的比较，当进行细细比较的时候，他发现不同就会把新值进行更新，从而达到了只更新变化的那一部分。
值得注意的是，每一个虚拟DOM都记录着自己的父节点，因此找到相应的父节点插入进入是比较容易的。总之新虚拟DOM在找寻父节点这一块永远和旧虚拟DOM保持一致就好了。
如果是文本节点，那么就会对比新虚拟DOM的文本与旧虚拟DOM的节点是否相同，如果不相同在这里进行更新的操作。如果不是文本节点，就对childen继续进行updateChilden进行递归的操作。直到找到最后一个节点。
等这里的代码运行结束，页面就被更新了，diff也完成了它应该做的任务。等diff函数栈执行完毕，最小量更新就完成了。
三、总结
1.最小量更新
在进行diff的时候，vue是遵循最小量更新的，也就是说，vue不在万不得已下是不会在页面上直接移出DOM节点而重新创建的，这个万不得已的条件就是如果节点类型变了，节点消失，节点新增等，这些才是必须要创建DOM的必要条件，其他情况都是在原来的DOM基础上进行修改，我们也可以在其中看到diff算法在这个过程中处理的颗粒度是很小的。
2.递归
diff毋庸置疑是用递归完成的，从根节点开始遵循深度优先遍历的原则，进行处理，更新DOM的过程就伴随着虚拟DOM的递归过程，等递归的调用栈结束后整个DOM树就被更新好了。
总结:那么本地的diff算法就总结到这里，其实还有很多细节是没有写到的，我也特别希望大家能够根据源码一个一个函数将他全部看明白，如果有错误的地方希望能够提出来，共同交流，那么本篇文章的结束就意味着vue2.0源码分析系列都介绍完了。再次感谢你的阅读！