探究Vue源码:深入理解diff算法

前言

在Vue中 组件初次渲染时，会调用 render 函数生成初始的虚拟 DOM 树。
当组件的状态发生变化时，Vue 会重新调用 render 函数生成新的虚拟 DOM 树。
而Diff 算法是用来比较新旧虚拟 DOM 树的差异，并且只对差异部分进行更新的算法,从而尽量减少性能开销。

虚拟DOM树是什么？

描述组件视图结构的虚拟节点树，也就是VNode树
,它描述了一个 DOM 节点的信息，包括节点类型、属性、子节点等。
实现vNode

function createVNode(type?,props?,children?){const vnode = {type,props,children,}return vnode 
}

运用虚拟 DOM 可以将真实 DOM 的操作转换为JS对象的操作，避免了频繁的直接操作真实 DOM 带来的性能损耗。我们可以运用虚拟DOM的属性来进行操作,vnode 的 children 数组中对应子节点的 vnode 对象，所以在 vue 中通过 vnode 和真实的 DOM 树进行映射，我们也称之为虚拟树。

实现Diff算法

锁定需要改变的位置 处理前置和后置没有改变的元素

预处理前置节点

定义一个头指针

function patchkeyChildren(c1,c2){let i = 0;//c1为旧let e1 = c1.length - 1;let e2 = c2.length - 1;function isSomeVNodeType(n1, n2) {return n1.type === n2.type && n1.key JJJ=== n2.key
}while (i <= e1 && i <= e2) {const n1 = c1[i]const n2 = c2[i]if (isSomeVNodeType(n1, n2)) {patch(n1, n2,...)} else {break;}i++;}
}

预处理后置节点

function patchkeyChildren(c1,c2,...){
...
...
while(i <= e1 && i <= e2) {const n1 = c1[e1]const n2 = c2[e2]if (isSomeVNodeType(n1, n2)) {
patch(n1, n2,... )
} else {
break;
}
e1--;e2--;}
}

3.处理仅有新增节点情况 新节点比老节点多

function patchkeyChildren(c1,c2,...){
...
...
if (i > e1) {
if (i <= e2) {
while (i <= e2) {
patch(null, c2[i],...)
i++;
}
}
}

4.处理仅有卸载节点情况也就是老节点比新节点多

老节点 a b c
新节点 a b

function patchkeyChildren(c1,c2,...){
...
...
if(i > e2){if(i <= e1){while(i <= e1){unmount(c1[i].el)}}
}
}

⭐️⭐️⭐️5.处理其他情况(新增/卸载/移动)

创建新的 在老的里面不存在，在新的里面存在

删除老的 在老的里面存在，新的里面不存在

移动 节点存在于新的和老的节点,但是位置变了

实现删除功能

两种方法查找新节点到底存在于老节点 一种方法是遍历 ，另一种是Key,Key是节点的唯一标识 能提高效率 这也是Vue中为何总要写key属性
定义s1、s2变量 分别记录要处理部分的起始位置

...
else{
let s1 = i;//旧节点开始位置
let s2 = i;//新节点开始位置const keyToNewIndexMap = new Map()
//遍历新节点保存key映射表
for (let i = s2; i <= e2; i++) {const nextChild = c2[i]keyToNewIndexMap.set(nextChild.key, i)}
}
for(let i = s1; i <= e1; i++){const prevChild = c1[i]let newindex;if (prevChild.key != null) {newIndex = keyToNewIndexMap.get(prevChild.key)} else {for (let j = s2; j <= e2; j++) {if (isSomeVNodeType(prevChild, c2[j])) {newIndex = j;break;}}
}
//如果没有找到 则直接删除旧节点中元素
if (newIndex === undefined) {unMount(prevChild.el)}else{patch(prevChild, c2[newIndex], ...)
}
}

优化 中间部分老的比新的多 那么多出来的可以直接删掉

const toBePatched = e2 - s2 + 1;
let patched = 0;for (let i = s1; i <= e1; i++) {
...
if (patched >= toBePatched) {unMount(prevChild.el)continue;}//在patch后
...
patched++

移动实现

这里就需要借助最长递增子序列算法提高效率了 因为要移动位置 要频繁dom操作，效率很慢，可以筛选那些老节点和新节点都有递增有顺序的节点不动

//先建立映射关系
const newIndexToOldIndexMap = new Array(toBePatched)
for (let i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
...
...
//在patch前实现
newIndexToOldIndexMap[newIndex - s2] = i + 1; //不能把值设为0 他是有特殊意义的patch(prevChild, c2[newIndex], container, ...)const increasingNewIndexSequence =getSequence(newIndexToOldIndexMap)
//指针
let j = 0
for(let i =0;i < toBePatched; i++){if(i !==increasingNewIndexSequence[j]){console.log("移动位置")}else{j++}
}

优化 调用最长递增子序列也会浪费一定性能 当 可以定义一个变量moved 如果移动再开始
没有移动则为false

let moved = false;
let maxNewIndexSoFar = 0;
...
if (newIndex >= maxNewIndexSoFar) {maxNewIndexSoFar = newIndex} else {moved = true}
...
const increasingNewIndexSequence = moved ? getSequence(newIndexToOldIndexMap) : []
if(moved){console.log('插入操作')
}

创建新的节点

if (newIndexToOldIndexMap[i] === 0) {
patch(null, nextChild)
}

实现完成. 完整代码

function patchKeyedChildren(c1: any, c2: any, container, parentComponent, parentAnchor) {let i = 0let e1 = c1.length - 1;let e2 = c2.length - 1function isSomeVNodeType(n1, n2) {return n1.type === n2.type && n1.key === n2.key}// 左侧while (i <= e1 && i <= e2) {const n1 = c1[i]const n2 = c2[i]if (isSomeVNodeType(n1, n2)) {patch(n1, n2, container, parentComponent, parentAnchor)} else {break;}i++;}while (i <= e1 && i <= e2) {const n1 = c1[e1]const n2 = c2[e2]if (isSomeVNodeType(n1, n2)) {patch(n1, n2, container, parentComponent, parentAnchor)} else {break;}e1--;e2--;}if (i > e1) {if (i <= e2) {const nextPos = e2 + 1;const anchor = e2 + 1 < c2.length ? c2[nextPos].el : nullwhile (i <= e2) {patch(null, c2[i], container, parentComponent, anchor)i++;}}} else if (i > e2) {while (i <= e1) {
//删除操作
hostRemove(c1[i].el)i++}} else { // Array to Array 中间乱序let s1 = i;let s2 = i;const keyToNewIndexMap = new Map()for (let i = s2; i <= e2; i++) {const nextChild = c2[i]keyToNewIndexMap.set(nextChild.key, i)}const toBePatched = e2 - s2 + 1;let patched = 0;const newIndexToOldIndexMap = new Array(toBePatched)// 中间值发生改变再调用方法let moved = false;let maxNewIndexSoFar = 0for (let i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0for (let i = s1; i <= e1; i++) {const prevChild = c1[i];if (patched >= toBePatched) {hostRemove(prevChild.el)continue;}let newIndex;if (prevChild.key != null) {newIndex = keyToNewIndexMap.get(prevChild.key)} else {for (let j = s2; j <= e2; j++) {if (isSomeVNodeType(prevChild, c2[j])) {newIndex = j;break;}}}if (newIndex === undefined) {hostRemove(prevChild.el)} else {if (newIndex >= maxNewIndexSoFar) {maxNewIndexSoFar = newIndex} else {moved = true}// 能代表新节点存在newIndexToOldIndexMap[newIndex - s2] = i + 1; //不能把值设为0 他是有特殊意义的patch(prevChild, c2[newIndex], container, parentComponent, null)patched++;}}const increasingNewIndexSequence = moved ? getSequence(newIndexToOldIndexMap) : []let j = increasingNewIndexSequence.length - 1;for (let i = toBePatched - 1; i >= 0; i--) {const nextIndex = i + s2;const nextChild = c2[nextIndex]const anchor = nextIndex + 1 < c2.length ? c2[nextIndex + 1].el : null;if (newIndexToOldIndexMap[i] === 0) {patch(null, nextChild, container, parentComponent, anchor)}if (moved) {if (j < 0 || i !== increasingNewIndexSequence[j]) {hostinsert(nextChild.el, container, anchor)} else {j--}}}}}
//递增子序列算法
function getSequence(arr: number[]): number[] {const p = arr.slice();const result = [0];let i, j, u, v, c;const len = arr.length;for (i = 0; i < len; i++) {const arrI = arr[i];if (arrI !== 0) {j = result[result.length - 1];if (arr[j] < arrI) {p[i] = j;result.push(i);continue;}u = 0;v = result.length - 1;while (u < v) {c = (u + v) >> 1;if (arr[result[c]] < arrI) {u = c + 1;} else {v = c;}}if (arrI < arr[result[u]]) {if (u > 0) {p[i] = result[u - 1];}result[u] = i;}}}u = result.length;v = result[u - 1];while (u-- > 0) {result[u] = v;v = p[v];}return result;}