Vue设计与实现：快速 Diff 算法
站长
· 阅读数 13
简单情况下的新旧两组子节点
相同的前置元素
开启一个while循环，让索引j从0开始递增，直到遇到不相同的节点为止
const oldVNode = {
type: 'div',
children: [
{ type: 'p', children: '1', key: 1 },
{ type: 'p', children: '2', key: 2 },
{ type: 'p', children: '3', key: 3 },
]
}
const newVNode = {
type: 'div',
children: [
{ type: 'p', children: '1', key: 1 },
{ type: 'p', children: '4', key: 4 },
{ type: 'p', children: '2', key: 2 },
{ type: 'p', children: '3', key: 3 },
]
}
解决思路：
- j从0开始，oldChildren、newChildren依次拿到对应j的vnode
- 判断对应j的oldVNode、newVNode的key是否相同
- 如果key相同就调用patch更新
function patchKeyedChildren(oldN, newN, container) {
const oldChildren = oldN.children
const newChildren = newN.children
// 处理相同的前置节点
// 索引 j 指向新旧两组子节点的开头
let j = 0
let oldVNode = oldChildren[j]
let newVNode = newChildren[j]
// while 循环向后遍历，直到遇到拥有不同 key 值的节点为止
while (oldVNode.key === newVNode.key) {
// 调用 patch 函数进行更新
patch(oldVNode, newVNode, container)
// 更新索引 j，让其递增
j++
oldVNode = oldChildren[j]
newVNode = newChildren[j]
}
}
结果：
相同得后置元素
由于新旧两组子节点的数量可能不一致，所以需要两个索引newEnd和oldEnd分别对应新旧两组子节点的后置索引
解决思路：
- 取oldChildren、newChildren的最后一个索引以及对应的最后一个节点
- 使用while比较oldChildren、newChildren的最后一个节点的key
- 如果key相同，就调用patch更节点，更新oldChildren、newChildren的最后一个索引以及对应的最后一个节点
function patchKeyedChildren(oldN, newN, container) {
const oldChildren = oldN.children
const newChildren = newN.children
// 处理相同的前置节点
// 索引 j 指向新旧两组子节点的开头
let j = 0
let oldVNode = oldChildren[j]
let newVNode = newChildren[j]
// while 循环向后遍历，直到遇到拥有不同 key 值的节点为止
while (oldVNode.key === newVNode.key) {
// 调用 patch 函数进行更新
console.log(oldVNode)
console.log(newVNode)
patch(oldVNode, newVNode, container)
// 更新索引 j，让其递增
j++
oldVNode = oldChildren[j]
newVNode = newChildren[j]
}
+ // 更新相同的后置节点
+ // 索引 oldEnd 指向旧的一组子节点的最后一个节点
+ let oldEnd = oldChildren.length - 1
+ // 索引 newEnd 指向新的一组子节点的最后一个节点
+ let newEnd = newChildren.length - 1
+
+ oldVNode = oldChildren[oldEnd]
+ newVNode = newChildren[newEnd]
+
+ while (oldVNode.key === newVNode.key) {
+ // 调用 patch 函数进行更新
+ patch(oldVNode, newVNode, container)
+ // 递减 oldEnd 和 nextEnd
+ oldEnd--
+ newEnd--
+ oldVNode = oldChildren[oldEnd]
+ newVNode = newChildren[newEnd]
+ }
}
结果：
新增节点
- 从新旧头部节点开始比较key，一直到不相同key为止，最终j会指向新旧不相同key的节点索引
- 当oldEnd<j，说明旧子节点已经遍历完
- 当newEnd>=j，说明新子节点索引j到newEnd之间有还有未处理的节点
解决思路：
- 当j > oldEnd && j <= newEnd成立，说明从 j --> newEnd 之间的节点应作为新节点插入
- 判断最新newEnd + 1的索引是否小于newChildren.length
- 小于就说明最新newEnd对应的不是尾部节点，拿到最新newEnd + 1对应子节点的真实dom作为锚点，将newChildren[j]插入在锚点前面
- 大于就说明是尾部节点，锚点为null，将newChildren[j]插入在锚点前面
- 当newEnd大于索引j说明新子节点遍历完，需要停止遍历
function patchKeyedChildren(n1, n2, container) {
const newChildren = n2.children
const oldChildren = n1.children
// 更新相同的前置节点
// 省略部分代码
// 更新相同的后置节点
// 省略部分代码
+ // 预处理完毕后，如果满足如下条件，则说明从 j --> newEnd 之间的节点应作为新节点插入
+ if (j > oldEnd && j <= newEnd) {
+ // 锚点的索引
+ const anchorIndex = newEnd + 1
+ // 锚点元素
+ const anchor = anchorIndex < newChildren.length ? newChildren[anchorIndex].el : null
+ // 采用 while 循环，调用 patch 函数逐个挂载新增节点
+ while (j <= newEnd) {
+ patch(null, newChildren[j++], container, anchor)
+ }
+ }
+
}
结果：
删除节点
const oldVNode = {
type: 'div',
children: [
{ type: 'p', children: '1', key: 1 },
{ type: 'p', children: '2', key: 2 },
{ type: 'p', children: '3', key: 3 },
]
}
const newVNode = {
type: 'div',
children: [
{ type: 'p', children: '1', key: 1 },
{ type: 'p', children: '3', key: 3 },
]
}
以现在的代码比较以上子节点，会出现newEnd < j,j >= oldEnd,也就是遍历完新子节点但旧子节点还没遍历完
解决思路：
- 当newEnd < j,j >= oldEnd,说明遍历完新子节点但旧子节点还没遍历完
- 遍历j -> oldEnd 之间的节点调用unmount卸载
- 当j>oldEnd说明旧子节点遍历完退出
function patchKeyedChildren(n1, n2, container) {
const newChildren = n2.children
const oldChildren = n1.children
// 更新相同的前置节点
// 省略部分代码
// 更新相同的后置节点
// 省略部分代码
if (j > oldEnd && j <= newEnd) {
// 省略部分代码
+ } else if (j > newEnd && j <= oldEnd) {
+ // j -> oldEnd 之间的节点应该被卸载
+ while (j <= oldEnd) {
+ unmount(oldChildren[j++])
+ }
+ }
}
结果：
复杂情况下的新旧两组子节点
const oldVNode = {
type: 'div',
children: [
{ type: 'p', children: '1', key: 1 },
{ type: 'p', children: '2', key: 2 },
{ type: 'p', children: '3', key: 3 },
{ type: 'p', children: '4', key: 4 },
{ type: 'p', children: '6', key: 6 },
{ type: 'p', children: '5', key: 5 },
]
}
const newVNode = {
type: 'div',
children: [
{ type: 'p', children: '1', key: 1 },
{ type: 'p', children: '3', key: 3 },
{ type: 'p', children: '4', key: 4 },
{ type: 'p', children: '2', key: 2 },
{ type: 'p', children: '7', key: 7 },
{ type: 'p', children: '5', key: 5 },
]
}
构造 source 数组
解决思路：
当处理完新旧子节点相同头尾节点，新的一组子节点中剩余未处理节点对应，创建一个source数组，数组中每一个元素分别跟未处理节点对应对应
if (j > oldEnd && j <= newEnd) {
// 省略部分代码
} else if (j > newEnd && j <= oldEnd) {
// 省略部分代码
+} else {
+ // 构造 source 数组
+ // 计算新的一组子节点中剩余未处理节点的数量
+ const count = newEnd - j + 1
+ const source = new Array(count)
+ source.fill(-1)
+}
新增、删除节点
解决思路：
- 先遍历新子节点newStart到newEnd，把新子节点key做为索引表的key，索引表的value为新子节点的索引
- 再遍历旧子节点，用旧子节点的key去索引表keyIndex去找
- 如果有对应的key那么就用patch比较更新
- 如果没有对应的key就说明旧子节点需要卸载，调用unmount卸载
if (j > oldEnd && j <= newEnd) {
// 省略部分代码
} else if (j > newEnd && j <= oldEnd) {
// 省略部分代码
} else {
const count = newEnd - j + 1
const source = new Array(count)
source.fill(-1)
+ // oldStart 和 newStart 分别为起始索引，即 j
+ const oldStart = j
+ const newStart = j
+ // 构建索引表
+ const keyIndex = {}
+ for (let i = newStart; i <= newEnd; i++) {
+ keyIndex[newChildren[i].key] = i
+ }
+ // 遍历旧的一组子节点中剩余未处理的节点
+ for (let i = oldStart; i <= oldEnd; i++) {
+ oldVNode = oldChildren[i]
+ // 通过索引表快速找到新的一组子节点中具有相同 key 值的节点位置
+ const k = keyIndex[oldVNode.key]
+
+ if (typeof k !== 'undefined') {
+ newVNode = newChildren[k]
+ // 调用 patch 函数完成更新
+ patch(oldVNode, newVNode, container)
+ // 填充 source 数组
+ source[k - newStart] = i
+ } else {
+ // 没找到
+ unmount(oldVNode)
+ }
+ }
}
结果：
判断节点是否需要移动
解决思路：
- 在遍历外定义moved、patched、pos，moved代表是否需要移动节点，pos代表遍历旧的一组子节点的过程中遇到的最大索引值k，patched代表更新过的节点数量
- 判断patched是否比需要更新的子字节数量大，大于就说明需要更新的子节点已更新完成，需要卸载多余的节点
- patched小于需要更新的子字节数量，旧子节点根据顺序遍历，旧子节点的key在索引表keyIndex中找到对应新子节点的key，用patch更新比较新旧子节点，patched+1
- 判断新子节点的key对应的索引是否大于最大索引值pos，如果大于，就把新子节点的索引赋值给最大索引值pos
- 再遍历比较新子节点的索引是否大于最大索引值pos，如果小于就说明该旧子节点需要移动
if (j > oldEnd && j <= newEnd) {
// 省略部分代码
} else if (j > newEnd && j <= oldEnd) {
// 省略部分代码
} else {
// 构造 source 数组
const count = newEnd - j + 1 // 新的一组子节点中剩余未处理节点的数量
const source = new Array(count)
source.fill(-1)
const oldStart = j
const newStart = j
+ // 新增两个变量，moved 和 pos
+ let moved = false
+ let pos = 0
const keyIndex = {}
for (let i = newStart; i <= newEnd; i++) {
keyIndex[newChildren[i].key] = i
}
+ // 新增 patched 变量，代表更新过的节点数量
+ let patched = 0
for (let i = oldStart; i <= oldEnd; i++) {
oldVNode = oldChildren[i]
const k = keyIndex[oldVNode.key]
+ if (patched <= count) {
if (typeof k !== 'undefined') {
newVNode = newChildren[k]
// 调用 patch 函数完成更新
patch(oldVNode, newVNode, container)
+ // 每更新一个节点，都将 patched 变量 +1
+ patched++
+ // 判断节点是否需要移动
+ if (k < pos) {
+ moved = true
+ } else {
+ pos = k
+ }
} else {
// 没找到
unmount(oldVNode)
}
} else {
// 如果更新过的节点数量大于需要更新的节点数量，则卸载多余的节点
unmount(oldVNode)
}
}
}
结果：
如何移动元素
最长递增子序列
给定一个数值序列，找到它的一个子序列，并且该子序列中的值是递增的，子序列中的元素在原序列中不一定连续。一个 序列可能有很多个递增子序列，其中最长的那一个就称为最长递增子序列
[ 0, 8, 4, 12 ]
// 最长递增子序列就是 [0, 8, 12]
使用lis函数计算一个数组的最长递增子序列，source数组的最长递增子序列为 [2, 3]，其中元素 2 在 该数组中的索引为 0，而数组 3 在该数组中的索引为 1，所以最终结果 为 [0, 1]。
function lis(arr) {
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) / 2) | 0
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
}
重新对节点进行编号
重新编号是为了让子序列 seq 与新的索引值产生对应关系
节点 p-1 和 p-5已经处理过，所以不需要编号，重新编号后，索引值为 0 和 1 的节点不需要移动。在 新的一组子节点中，节点 p-3 的索引为 0，节点 p-4 的索引为 1，所 以节点 p-3 和 p-4 所对应的真实 DOM 不需要移动。换句话说，只有 节点 p-2 和 p-7 可能需要移动
挂载新节点
解决思路：
- for循环的目的是让变量i就是节点的索引按照上图中箭头的方向移动， 以便能够逐个访问新的一组子节点中的节点
- 因为i是递减的，所以在for循环中先判断source[i]是否为-1也就是新增节点，i是当前节点在剩余未处理新子节点的数量的索引，所以+newStart（已处理过的头部节点）会得到在新子节点中真实索引值，根据真实索引值pos拿到对应新子节点newVNode
- 判断pos + 1是否小于新子节点的长度，小于就说明新子节点newVNode不是尾部节点，把newChildren[nextPos].el赋值给anchor，大于就说明是尾部节点，把null赋值给anchor，最终调用patch对比更新
- 判断当前节点的索引i是否跟seq[s]最长递增子序列的最后一个元素相同，如果不相同就说明需要移动，相同就让s指向下一个位置
if (moved) {
const seq = lis(sources)
// s 指向最长递增子序列的最后一个元素
let s = seq.length - 1
// i 指向新的一组子节点的最后一个元素
let i = count - 1
// for 循环使得 i 递减，即按照上图中箭头的方向移动
for (i; i >= 0; i--) {
if (source[i] === -1) {
// 说明索引为 i 的节点是全新的节点，应该将其挂载
// 该节点在新 children 中的真实位置索引
const pos = i + newStart
const newVNode = newChildren[pos]
// 该节点的下一个节点的位置索引
const nextPos = pos + 1
// 锚点
const anchor = nextPos < newChildren.length
? newChildren[nextPos].el
: null
// 挂载
patch(null, newVNode, container, anchor)
} else if (i !== seq[s]) {
// 如果节点的索引 i 不等于 seq[s] 的值，说明该节点需要移动
} else {
// 当 i === seq[s] 时，说明该位置的节点不需要移动
// 只需要让 s 指向下一个位置
s--
}
}
}
结果：
移动节点
解决思路：
移动节点的实现思路类似于挂载全新的节点。不同点在于，移动节点是通过 insert 函数来完成的
if (moved) {
const seq = lis(sources)
// s 指向最长递增子序列的最后一个元素
let s = seq.length - 1
let i = count - 1
for (i; i >= 0; i--) {
if (source[i] === -1) {
// 省略部分代码
} else if (i !== seq[s]) {
+ // 说明该节点需要移动
+ // 该节点在新的一组子节点中的真实位置索引
+ const pos = i + newStart
+ const newVNode = newChildren[pos]
+ // 该节点的下一个节点的位置索引
+ const nextPos = pos + 1
+ // 锚点
+ const anchor = nextPos < newChildren.length
+ ? newChildren[nextPos].el
+ : null
+ // 移动
+ insert(newVNode.el, container, anchor)
} else {
// 当 i === seq[s] 时，说明该位置的节点不需要移动
// 并让 s 指向下一个位置
s--
}
}
}
结果：
