updateChildren
终于到这最复杂的一步了。首先，我先说一下这一步的作用以及具体做了些什么
作用：用于比较新旧两个vnode的子节点
那具体做了什么，怎么比较的。
比较规则
声明：下文中所指的匹配上，指的就是判断是否是sameVnode，即上文中所说的，key相同，sel选择器相同
首先，会将新旧vnode的子节点（oldCh, Ch）提取出来，并分别加上两个指针oldStart, oldEnd, newStart, newEnd。分别指向odlCh的第一个节点，oldCh的最后一个节点，Ch的第一个节点，Ch的最后一个节点
比较时，会优先拿oldStart<—>newStart，oldStart<—>newEnd，oldEnd<—>newStart，oldEnd<—>newEnd 两两进行对比。如果匹配上，那么会将旧节点对应的真实dom移到新节点的位置上。并将匹配上了的指针往中间移动。同时匹配上了的两个节点会继续指向patchVnode函数去进一步比对（指针的移动相当于永远保持指针中间的节点还是尚未匹配状态，已经匹配到的移到指针外面去）
如果上面4种比较都没有匹配上，那么这个时候，有key和没key处理方式就不一样了。具体怎么处理，后面会细说。
当oldStart > oldEnd 或者 newStart > newEnd时，结束对比。此时
1、如果是oldStart > oldEnd，代表oldCh都已匹配完成，而此时，如果newStart <= newEnd，那么代表 newStart 和 newEnd直接的节点为新增节点。那么真实dom会在当前newStart 和newEnd之间新增newStart 和 newEnd中间还未匹配的节点。
2、如果是newStart > newEnd，代表Ch全都已经匹配完成，而此时，如果oldStart 和 newEnd之间还有节点，则说明，这些节点是原来存在的，但现在没有了，此时真实dom删除这些节点。
此时，比较结束。
下面，我们通过图例来进一步理解
上图表示的就是oldCh 和 Ch。那么怎么来比较。我们一一来看每一种情况
- 1.oldStart 和 newStart相同
指针后移后，
2.oldStart 和 newEnd相同，此时会将oldStart对应的真实dom移动newEnd对应的位置我们就以上图为例了，不重新画图了，上图，oldStart 和 newEnd相同，此时真实dom会将b移动最末尾。同时oldStart 和 newEnd指针向中间移
3.oldEnd 和 newEnd相同 。我们还是以上图为例（就是这么巧，上图刚好oldEnd和 newEnd相同，哈哈）c 和 c相同，oldEnd 和 newEnd往中间移动，并执行patchVnode（oldc，newc）
4.oldEnd和newStart相同的我们后面再画，根据上图，我们继续将oldStart > oldEnd的情况。上图中，oldStart 大于 oldEnd，说明oldCh已经全部匹配完，而此时newCh中，newStart 和 newEnd之间还有个e没有匹配。那说明e是新增节点。此时真实dom会在newStart和newEnd之间新增还未匹配的dom（新增节点执行addVnodes函数）
- 此时，整个oldCh和newCh的比较就已经完成了。可以看到，此时，真实dom已经变成和newCh的一样了。
- 5.oldEnd 和 newStart 相同时
此时，oldEnd所对应的真实dom会移动newStart所在位置，然后oldEnd 和 newStart指针往中间移动。移动后，如下图
6.当newStart > newEnd的时候，此时，如果oldStart 和 oldEnd之间还存在没有匹配完成的节点时，那么认为，oldCh中，那么还没匹配到的节点在新的虚拟dom树上已经没有了，此时，执行删除操作（removeVnodes函数），删除还oldStart和oldEnd之间的节点。
好了，现在前面4种情况以及两种匹配结束时的情况我们已经说完了。现在就剩最后一种情况，即：头尾分别都没匹配上，且没有结束比较的时候。我们继续来看第7种情况。
7.当前面（1，2，3，5）这4种情况都匹配不到时，会拿当前newStart指针所指的那个节点去和oldCh中找。看是否能找到。这个时候，就要看是不是存在key了。因为首先，会建立一个oldCh中key和index的一个映射表，格式为{key: idx}。如果都没有key，那么映射表为空对象{}。此时会有3种情况
1、如果newStart指针所指的节点不存在key，那么不会去oldCh中寻找和这个一样的节点。而是直接新增newStart所指的这个节点，新增后，newStart指针后移
2、如果newStart指针所指的节点存在key，那么会去oldCh的key和Idx的映射表中寻找newStart节点的key是否存在。如果不存在，那么默认newStart节点为新增节点。真实dom会在newStart位置直接新增节点。新增完成后，指针后移
3、同样newStart指针所指的节点存在key，那么去oldCh的映射表中查找。此时如果找到了。那么会继续判断key相同的这两个节点的sel选择器是否相同。如果也相同，那么默认这是同一个节点，那么真实节点会将匹配到的节点，移到newStart对应的位置，然后执行patchVnode(oldVnode, newVnode)进行进一步对比。同时newStart指针后移。而oldCh中被匹配到的那个位置，置为undefined。
总体过程就是这样，然后不停的patchVnode，updateChildren循环递归下去，知道oldVode和newVnode所有节点都对比完成。下面附上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 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { if (oldStartVnode == null) { // 这一步的操作是始终保证oldStartVnode为oldStartIdx指针所指向的那个节点 oldStartVnode = oldCh[++oldStartIdx] } else if (oldEndVnode == null) { // 这一步的操作是始终保证oldEndVnode为oldEndIdx指针所指向的那个节点 oldEndVnode = oldCh[--oldEndIdx] } else if (newStartVnode == null) { // 这一步的操作是始终保证newStartVnode为newStartIdx指针所指向的那个节点 newStartVnode = newCh[++newStartIdx] } else if (newEndVnode == null) { // 这一步的操作是始终保证newEndVnode为newEndIdx指针所指向的那个节点 newEndVnode = newCh[--newEndIdx] } else if (sameVnode(oldStartVnode, newStartVnode)) { // oldStart和newStart相同时，执行patchVnode进一步比较 patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue) oldStartVnode = oldCh[++oldStartIdx] // 并将指针往中间移动 newStartVnode = newCh[++newStartIdx] // 并将指针往中间移动 } else if (sameVnode(oldEndVnode, newEndVnode)) { // oldEnd和newEnd相同时，执行patchVnode进一步比较 patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue) oldEndVnode = oldCh[--oldEndIdx] // 并将指针往中间移动 newEndVnode = newCh[--newEndIdx] // 并将指针往中间移动 } else if (sameVnode(oldStartVnode, newEndVnode)) { // oldStart和newEnd相同时，执行patchVnode进一步比较 patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue) api.insertBefore(parentElm, oldStartVnode.elm!, api.nextSibling(oldEndVnode.elm!)) oldStartVnode = oldCh[++oldStartIdx] // 并将指针往中间移动 newEndVnode = newCh[--newEndIdx] // 并将指针往中间移动 } else if (sameVnode(oldEndVnode, newStartVnode)) { // oldEnd和newStart相同时，执行patchVnode进一步比较 patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue) api.insertBefore(parentElm, oldEndVnode.elm!, oldStartVnode.elm!) oldEndVnode = oldCh[--oldEndIdx] // 并将指针往中间移动 newStartVnode = newCh[++newStartIdx] // 并将指针往中间移动 } else { // 这里面就是当前面4种情况都不匹配时的处理结果 if (oldKeyToIdx === undefined) { // 存在key的情况下 得到oldCh中 key和idx的一个映射关系，格式为{key: idx}, oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) } idxInOld = oldKeyToIdx[newStartVnode.key as string] // 通过key,找到当前key的节点在oldCh中的位置，如果找不到会返回undefined if (isUndef(idxInOld)) { // 如果是undefind，说明newStartVnode的节点的key在oldCh中不存在，或者newStartVnode没有key // 此时会直接创建新的节点，所以key的设置，会优化比较步骤 api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm!) } else { // 如果找到了newStartVnode的可以在oldCh中的位置，说明可能只是移动了位置。 elmToMove = oldCh[idxInOld] // 获取需要移动的旧节点 if (elmToMove.sel !== newStartVnode.sel) { // 如果旧节点和新节点的sel不同，代表变了（比如原来是div，现在变成了p） // 新增新的节点 api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm!) } else { // sel相等，说明是相同节点，那么patchVnode进一步进行比较 patchVnode(elmToMove, newStartVnode, insertedVnodeQueue) oldCh[idxInOld] = undefined as any // 真实节点移动到相应的位置 api.insertBefore(parentElm, elmToMove.elm!, oldStartVnode.elm!) } } // newStart指针往中间移 newStartVnode = newCh[++newStartIdx] } } if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) { // 如果比对结束 if (oldStartIdx > oldEndIdx) { // newCh的start和end之间还有节点时，新增这些节点 before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].elm addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue) } else { // 否则 oldCh的start和end之间还有节点时，移除这些节点 removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx) } } }
总结
我们在最后整理一下步骤。
1、比较两个虚拟dom树，对根节点root进行执行patch(oldVnode，newVnode)函数，比较两个根节点是否是相同节点。如果不同，直接替换（新增新的，删除旧的）
2、如果相同，对两个节点执行patchVnode（oldVnode, newVnode），比较属性，文本，已经子节点。此时，要么新增，要么删除。要么直接修改文本内容。只有当都存在子节点时，并且oldVnode === newVnode 为false时。会执行updateChildren函数，去进一步比较他们的子节点。
3、比较分3大类。
第一类：oldStart === newStart， oldStart === newEnd，oldEnd === newStart，oldEnd === newEnd 这4种情况的比较。如果这4种情况中任何一种匹配。那么会执行patchVnode进一步比较。同时指针往中间移
第二类：oldStart > oldEnd 或者 newStart > newEnd时。表示匹配结束。此时，多余的元素删除，新增的元素新增。
第三类：上面几种情况都不匹配。那么这个时候key是否存在。就起到关键性作用了。存在key时，可以直接通过key去找到节点的原来的位置。如果没有找到，就新增节点。找到了，就移动节点位置。查找效率非常高
而如果没有key呢，那么压根就不会去原来的节点中查找了。而是直接新增这个节点。这就导致这个节点下的所有子节点都会被重新新增。会出现明显的性能损耗。所以，合理的应用key，也是一种性能上的优化。
总之一句话。diff的过程，就是一个 patch —> patchVnode —> updateChildren —> patchVnode —> updateChildren —> patchVnode… 这样的一个循环递归的过程
题外话 diff和数据劫持的共同工作原理
另外，我这里再插一句。可能有的人会疑惑了，那我通过这个虚拟dom的diff算法，就能精准的知道被更新的地方在哪，然后去更新变动的部分。那我vue靠这个就够了呀。我为什么还需要数据劫持呢，还需要getter，setter呢。没错，其实单单靠虚拟dom的diff确实是可以实现的。比如react就是这么做的。react精确查找数据的更新就是纯用虚拟dom的diff的。
但是这会产生一个什么问题呢。当项目非常大的时候，dom树是非常复杂的，如果每次一个小小的改动，就要通过diff算法去精确找到改动的地方，那么这个计算量是非常大的。产生的性能损耗也会巨大。这显然是不合理的。那么vue和react分别是怎么解决这个问题的
vue: 了解vueMVVM原理的人应该都清楚，vue通过Object.defineproperty的数据劫持，会劫持到每一个状态数据，给他们加上getter，setter。并且创建一个发布者Dep,同时，会给依赖这个状态数据的每个依赖者添加一个订阅者watcher。这样，当数据发生变化时，会触发对应的setter，从而Dep会发布通知，通知每一个订阅者watcher，然后watcher更新对应的数据。但是，如果任何一个数据的依赖我都增加一个watcher。那么项目中的watcher数量是会非常庞大的。细粒度太高，会带来内存和依赖关系维护的巨大消耗。这样一种情况下，vue采用响应式+diff的方式。通过响应式的getter,setter快速知道数据的变化发生在哪个组件中，然后组件内部再通过diff的方式去获取更详细的更新情况，并更新数据。
react: 而react却是通过他的一个生命周期函数shouldComponentUpdate实现的。通过手动在这个生命周期函数中判断当前组件的数据是否有发生变化，来决定当前组件是否需要更新。这样，没有发生状态数据变化的组件就不需要进行diff。从而缩小diff的范围。
好了，今天的文章就写到这了。如果有问题，欢迎评论！！
