diff算法-patch函数（三）

前言

diff算法主要是三步：生成虚拟节点、将新旧虚拟节点对比（核心）、新节点替换旧节点。本篇文章主要讲如何实现patch函数中最后一部分，也是最核心的一部分。

介绍

前面已经把，不同节点的情况和相同节点且旧节点没有子节点情况讲解了，这篇文章来介绍以下，相同节点情况下，旧虚拟虚拟节点有子节点并且新虚拟节点也有子节点的情况，需要按照规定的比较顺序比较，比较的规则如下：

为了方便书写，我会进行简写：

旧前：旧虚拟节点的头部指针

旧后：旧虚拟节点的尾部指针

新前：新虚拟节点的头部指针

新前：新虚拟节点的头部指针

比较会有六种情况：

比较永远都是从第一种情况开始匹配！！！

1.旧前 – 新前
2.旧后 – 新后
3.旧前 – 新后
4.旧后 – 新前
5.查找
6.创建或者删除

情况一：旧前 – 新前

情况一匹配成功，此时旧前和新前的指针会++

情况二：旧后 – 新后

情况二匹配成功，此时旧后和新后的指针会–

情况三：旧前 – 新后

情况二匹配成功，此时旧前会++和新后的指针会–

情况四：旧后 – 新前

情况二匹配成功，此时旧后会–和新前的指针会++

情况五：查找

新节点添加到页面，并且如果旧节点有新节点的值，那么旧节点值赋值为undefined

实现

首先，我们需要为新旧虚拟节点添加key值，并且创建一个updateChildren()方法，用来处理旧虚拟虚拟节点有子节点并且新虚拟节点也有子节点的情况

创建updateChildren

根据上面的分析，分为以下几种情况：

• 情况一：旧前和新前如果旧前节点的key和新前节点的key相同，情况一规则命中deepPatch(oldStartVnode, newStartVnode)if (newStartVnode) newStartVnode.elm = oldStartVnode.elmoldStartVnode = oldCh[++oldStartIdx]newStartVnode = oldCh[++newStartIdx] * 情况二：旧后和新后如果旧后节点的key和新后节点的key相同，情况二规则秒中deepPatch(oldEndVnode, newEndVnode)if (newEndVnode) newEndVnode.elm = oldEndVnode.elmoldStartVnode = oldCh[++oldStartIdx]newStartVnode = newCh[++newStartIdx] * 情况三：旧前和新后如果旧前节点的key和新后节点的key相同，情况二规则秒中deepPatch(oldStartVnode, newEndVnode)if (newEndVnode) newEndVnode.elm = oldEndVnode.elm// 把旧前指定的节点移动到旧后指定的节点的后面parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm)oldStartVnode = oldCh[++oldStartIdx]newEndVnode = newCh[--newEndIdx] * 情况四：旧后和新前如果旧后节点的key和新前节点的key相同，情况二规则秒中deepPatch(oldEndVnode, newStartVnode)if (newStartVnode) newStartVnode.elm = oldEndVnode.elm// 将旧后指定节点移动到旧前指定的节点前面parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm)oldEndVnode = oldCh[--oldEndIdx]newStartVnode = newCh[++newStartIdx] * 情况五：查找* 最后进行新增和删除> 主要分两种情况：旧前指针大于旧后指针、新前指针大于新后指针* 旧前指针大于旧后指针> 此时进行新增操作const before = newCh[newEndIdx + 1] ? newCh[newEndIdx + 1].elm : nullfor (let i = newStartIdx; i <= newEndIdx; i++) {parentElm.insertBefore(createElement(newCh[i]), before)} * 新前指针大于新后指针> 此时进行删除操作for (let i = oldStartIdx; i <= oldEndIdx; i++) {parentElm.removeChild(oldCh[i].elm)} 代码

updateChildren.js

import deepPatch from "./deepPatch";
import patch from "./patch";
import createElement from "./createElement";

// 判断两个虚拟节点是否为同一个节点
function sameVnode(vNode1, vNode2) {return vNode1.key == vNode2.key

}
// parentElm 真实DOM , oldCh 旧的虚拟节点, newCh 新的虚拟节点
export default (parentElm, oldCh, newCh) => {let oldStartIdx = 0 // 旧前指针let oldEndIdx = oldCh.length - 1 // 旧后指针let newStartIdx = 0 // 新前指针let newEndIdx = newCh.length - 1 // 新后指针let oldStartVnode = oldCh[0] // 旧前虚拟节点let oldEndVnode = oldCh[oldEndIdx] // 旧后虚拟节点let newStartVnode = newCh[0] // 新前虚拟节点let newEndVnode = newCh[newEndIdx] // 新后虚拟节点while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {if (oldStartVnode == undefined) {oldStartVnode = oldCh[++oldStartIdx]}if (oldEndVnode == undefined) {oldEndVnode = oldCh[--oldEndVnode]} else if (sameVnode(oldStartVnode, newStartVnode)) {console.log(oldStartVnode)// 第一种情况：旧前和新前console.log('情况1')deepPatch(oldStartVnode, newStartVnode)if (newStartVnode) newStartVnode.elm = oldStartVnode.elmoldStartVnode = oldCh[++oldStartIdx]newStartVnode = oldCh[++newStartIdx]} else if (sameVnode(oldEndVnode, newEndVnode)) {// 第二种情况：旧后和新后console.log('情况2')deepPatch(oldEndVnode, newEndVnode)if (newEndVnode) newEndVnode.elm = oldEndVnode.elmoldStartVnode = oldCh[++oldStartIdx]newStartVnode = newCh[++newStartIdx]} else if (sameVnode(oldStartVnode, newEndVnode)) {// 第三种情况：旧前和新后console.log('情况3')deepPatch(oldStartVnode, newEndVnode)if (newEndVnode) newEndVnode.elm = oldEndVnode.elm// 把旧前指定的节点移动到旧后指定的节点的后面parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm)oldStartVnode = oldCh[++oldStartIdx]newEndVnode = newCh[--newEndIdx]} else if (sameVnode(oldEndVnode, newStartVnode)) {// 第四种情况：旧后和新前console.log('情况4')deepPatch(oldEndVnode, newStartVnode)if (newStartVnode) newStartVnode.elm = oldEndVnode.elm// 将旧后指定节点移动到旧前指定的节点前面parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm)oldEndVnode = oldCh[--oldEndIdx]newStartVnode = newCh[++newStartIdx]} else {// 第五种情况：查找console.log('情况5')// 创建一个对象，存虚拟节点的（判断新旧有无相同节点）const keyMap = {}for (let i = oldStartIdx; i <= oldEndIdx; i++) {const key = oldCh[i].keyif (key) keyMap[key] = i}// 在旧节点种寻找新前指向的节点let idxInOld = keyMap[newStartVnode.key]// 如果有，说明数据在新旧虚拟节点中都存在if (idxInOld) {const elmMove = oldCh[idxInOld]deepPatch(elmMove, newStartVnode)// 处理过的节点，在旧虚拟节点的数组种，设置为undefineoldCh[idxInOld] = undefinedparentElm.insertBefore(elmMove.elm, oldStartVnode.elm)} else {// 如果没有找到，说明是一个新的节点（创建）parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm)}// 新数据（指针）+1newStartVnode = newCh[++newStartIdx]}}// 结束while 只有两种情况（新增和删除）// 1. oldStartIdx > oldEndIdx// 2. newStartIdx > newEndIdxif (oldStartIdx > oldEndIdx) {const before = newCh[newEndIdx + 1] ? newCh[newEndIdx + 1].elm : nullfor (let i = newStartIdx; i <= newEndIdx; i++) {parentElm.insertBefore(createElement(newCh[i]), before)}} else {// 进入删除操作for (let i = oldStartIdx; i <= oldEndIdx; i++) {parentElm.removeChild(oldCh[i].elm)}}
} 
1
2
3
4
5
6
7
8
9
10
11

演示

示例一：

示例二：

旧前 – 新后 => 旧后 – 新前 => 旧前 – 新前 => 旧前 – 新前

比较永远都是从第一种情况开始匹配！！

示例三：

当新节点数大于旧节点数，此时需要新增节点

示例四：

当新节点数小于旧节点数，此时需要删除节点

总结

updateChildren函数是diff算法的核心函数，也是diff算法种最复杂的部分，负责旧虚拟节点和新虚拟节点均存在子节点的情况，在更新节点时，会按照特定的规则进行替换，一共有五种规则：

1.旧前 – 新前
2.旧后 – 新后
3.旧前 – 新后
4.旧后 – 新前
5.查找

核心函数，也是diff算法种最复杂的部分，负责旧虚拟节点和新虚拟节点均存在子节点的情况，在更新节点时，会按照特定的规则进行替换，一共有五种规则：

1.旧前 – 新前
2.旧后 – 新后
3.旧前 – 新后
4.旧后 – 新前
5.查找

最后再根据新旧节点个数，判断需要新增节点还是删除节点操作。