Vue3 快速 Diff 算法简明指南

有两个数组 oldVNodes 和 newVNodes, VNode 结构为 { id: 唯一值, text: string }

请设计一个 diff 方法，将 oldVNodes 转换为 newVNodes 数组

const oldVNodes = [
	{
		id: 1,
		text: '1',
	},
	{
		id: 2,
		text: '2',
	},
	{
		id: 3,
		text: '3',
	},
	{
		id: 4,
		text: '4',
	}
];

const newVNodes = [
	{
		id: 1,
		text: '11',
	},
	{
		id: 3,
		text: '33',
	},
	{
		id: 2,
		text: '22',
	},
	{
		id: 5,
		text: '5'
	},
	{
		id: 4,
		text: '4',
	}
];

思路

采用 Vue3 子节点快速 Diff 算法思路

1. 类似文本 Diff, ‘abcdefg’ → ‘abfedsg’, 去掉头尾相同的节点，’ab’ 和 ‘g’
2. 增加/删除节点
3. 判断是否需要移动
4. 找到旧节点的最小递增子序列，然后从后往前判断，若索引相同则无需移动，只要更新即可，若索引不同则调用 insertBefore 方法移动

基础方法

// 更新/新增节点
function patch(oldVNode, newVNode, container, anchor) {
    if (!oldVNode && !newVNode) return null;
	  // oldVNode 为空
	  if (oldVNode === null) {
		  container.splice(anchor, 1, {
			  id: newVNode.id,
			  text: newVNode.text,
		  })
	  }
	  
    // 普遍情况
    // 更新 text
    oldVNode.text = newVNode.text;
}

// 删除节点
function unmount(container, index) {
	container.splice(index, 1);
}

// 交换顺序采用 insertBefore, 模拟 Dom 的 insertBefore
function insertBefore(container, node, index) {
	// 找到元素
	const findIndex = container.findIndex(item => item === node);
	// 删除旧元素
	container.splice(findIndex, 1);
	// 插入新元素
	container.splice(index - 1, 0, node);
	return container;
}

function isEqual(vnode1, vnode2) {
  if (vnode1 == null || vnode2 == null) return false;
	return vnode1.id === vnode2.id;
}

主流程

function patchChildren(oldChildren, newChildren) {
	let equalStartIdx = 0, oldEndIdx = oldChildren.length - 1,
		newEndIdx = newChildren.length - 1;
	// 1. 预处理
	// 1.1 把头部相同的节点都更新值
	while(isEqual(oldChidlren[equalStartIdx], newChildren[equalStartIdx ])){
			patch(oldChildren[equalStartIdx], newChildren[equalStartIdx])
			equalStartIdx++;
	}
	// 1.2 把尾部相同的节点都更新值
	while(oldEndIdx >= 0 && newEndIdx >= 0){
		if (isEqual(oldChildren[oldEndIdx], newChildren[newEndIdx])) {
			patch(oldChildren[oldEndIdx--], newChildren[newEndIdx--])
		}
	}
	
	if (euqalStartIdx > oldEndIdx && equalStartIdx <= newEndIdx) {
		// 添加新节点
		const anchor = newEndIdx + 1;
		while(euqalStartIdx <= newEndIdx) {
			patch(null, newChildren[euqalStartIdx++], oldChildren, anchor)
		}
		
	} else if (euqalStartIdx <= oldEndIdx && equalStartIdx > newEndIdx) {
		// 删除节点
		while(equalStartIdx <= oldEndIdx) {
			unmount(oldChildren, equalStartIdx++);
		}
	} else {
				// 生成 source 数组（新节点在旧节点的位置）后续用来做最长递增子序列并且判断是否需要移动
				let needMove = false; // 如果 source 不是单调递增的话则需要 moved
				// 生成 source 数组
				const count = newEndIdx - equalStartIdx + 1;
				const source = new Array(count).fill(-1);
				const newKeys = {};
				for(let j = equalStartIdx;j <= newEndIdx ;j++) {
					newKeys[newChildren[j].id] = j;
				}
				let preIdx = -1;
				for(let i = equalStartIdx;i <= oldEndIdx ;i++) {
						const newKeyIndex = newKeys[oldChildren[i].id];
						// 旧节点在新数组里不存在则需要 unmount
						if (newKeyIndex === undefined) {
							unmount(oldChildren, i);
						} else {
								if (isEqual(newChildren[j], oldChildren[i])) {
									source[i - equalStartIdx] = i;
									patch(oldChilren[i], newChildren[i], oldChilren)
									if (i >= preIdx) {
										preIdx = i;
									} else {
										needMove = true;
									}
								}
						}
				}
				if (needMove === true) {
						// 生成最长递增子序列(存放的是索引)
						const lis = findLIS(oldChildren, source);
						// 最小化移动节点
						// 从后开始判断索引位置与LIS的是否相同，若不同则需要移动
						let lastLISIndex = lis.length - 1;
						let lastNewChildrenIdx = count - 1;
						for(;lastNewChildrenIdx >= 0;lastNewChildrenIdx--)
							if (source[lastNewChildrenIdx] === -1) {
								// 新节点
								const pos = lastNewChildrenIdx + equalStartIdx;
								const nextPos = pos + 1;
								const anchor = nextPos < newChildren.length ? nextPos : null;
								patch(null, newChildren[lastNewChildrenIdex], oldChildren, anchor);
							} else if (lastNewChildrenIdx !== lis[lastLISIndex]) {
								// 需要移动
								const pos = lastNewChildrenIdx + equalStartIdx;
								const nextPos = pos + 1;
								const anchor = nextPos < newChildren.length ? nextPos: null;
								insertBefore(nextChildren[lastNewChildrenIdx], oldChildren, anchor);
							} else {
								patch(oldChilren[lastNewChildrenIdx], newChildren[lastNewChildrenIdx], oldChildren)
								lastLISIndex--;
							}
						}
				}
				
	}

}

找到最长递增子序列

// [1,2,100, 3,9, 101,-2, 888, -10]
// 最长递增子序列是 [1,2,3,9,101,888]

const findLIS = function (arr = []) {
	if (arr.length === 0) return [];
	const dp = new Array(arr.length).fill(1);
	const prev = new Array(arr.length).fill(-1); 

	let maxLength = 1;
	let maxIndex = 0;
	for(let i = 0;i < arr.length;i++) {
		for(let j = 0;j < i;j++) {
			if (arr[i] > arr[j] && dp[j] + 1 > dp[i]) { 
				dp[i] = dp[j] + 1;
				prev[i] = j; // 满足比当前元素小的最后一个的索引
			}
		}
		if (dp[i] > maxLength) {
			maxLength = dp[i];
			maxIndex = i;
		}
	}

	// 从 maxIndex 开始，根据 prev 数组，找到最长递增子序列
	const result = [];
	let current = maxIndex;
	while(current !== -1) {
		result.unshift(current);
		current = prev[current];
	}

	return result;
}