Vue3中的diff算法
Posted by Mars . Modified at
一、Vue3中的diff算法
Vue3中对于没有key的片段，采用的是直接数组比较方法；
对于有key的片段，采用的是先掐头去尾，然后执行最长递增子序列的方法。
1. 最长递增子序列算法
最长递增子序列算法：
贪心策略：为了找到最长的递增子序列，我们希望递增序列增长得慢一些。这样后面的元素就更容易与其形成更长的递增子序列。
因此，假设我们在遍历过程中当前找到的最长递增子序列是sub，此时sub末尾（最大）的元素是a，当位于后面的元素b比a更小，我们应该更新a为b，因为此时b比a更容易实现最长的递增子序列。
// By Mars 2021.09.06
// Get max asscending sequence of an pure number array.
// getMaxSequence(arr);
// eg. [2,3,6,1,7] -> [2,3,6,7]
// Algorithum (greedy) :
// Time: O(n*logn)
// Steps:
// 1. Maintain an accending order array:[result], and an array:[p] whose length is the same with given array.
// 2. result[i] = n, means that at current status, we have found a max accending sequence of length i+1, and the minimum number at the tail of the sequence is [n].
// 3. p[i] is setted when we take an element form the original given array and refresh the result array with it. p[i] records the previous number of result array of where we put the current element array[i] into at the result array;
// 4. result array is an accending array, we iterate the original array and pick current element (arr[i]), then find the first element which is larger than current element in result array (assume that position is [pos]), and replace it with current element value;
// 5. then we get the previous element of result array (result[pos-1]), and set p[i] with it;
// 6. after we iterate all the elements, the last element of result array must be the real number of the max sequence, other elements can be replaced during the precess above, so they may be not the real number of the result max sequence;
// 7. Luckily, we record the real element when we refresh every element of result, which is in array p.
// 8. everytime, we get the element of result array, and find the position of it in the original array [pos], the real previous element of max subsquence is p[pos];
// 9. repeat the step.8 until all the sequence is found.
function getMaxSequence(arr) {
let result = [];
let p = arr.slice(); // same length of arr.
function bs(tar) {
// find the first num which [ >= tar ].
let l = 0,
r = result.length - 1;
while (l < r) {
let m = Math.floor((l + r) / 2);
if (arr[result[m]] >= tar) r = m;
else l = m + 1;
}
return l;
}
for (let i = 0; i < arr.length; i++) {
if (result.length === 0) {
result.push(i);
p[i] = null;
} else {
let pos = bs(arr[i]);
if (arr[result[pos]] >= arr[i]) {
if (pos === 0) {
result[pos] = i;
p[i] = null;
} else {
result[pos] = i;
p[i] = result[pos - 1];
}
} else {
p[i] = result[result.length - 1];
result.push(i);
}
}
}
let cur = result.length;
let prev = result[result.length - 1];
while (cur > 0) {
cur -= 1;
result[cur] = prev;
prev = p[result[cur]];
}
return result;
}
2. 无key元素的diff算法
没有key的元素片段，patch的时候采用的是直接进行数组比较的方法。
// 基本思路：
// 1. 对oldChildren, newChildren，选取二者中长度较小的作为公共长度；
// 2. 从0位置开始，对公共长度部分一一对应直接patch；
// 3. 如果oldChildren长度更长，则把多余的部分直接unmount；
// 4. 如果newChildren长度更长，则直接把剩余的部分依次mount到最下方。
const patchUnkeyedChildren = (c1, c2, container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized) => {
c1 = c1 || EMPTY_ARR;
c2 = c2 || EMPTY_ARR;
// Choose the common length of c1 and c2.
const oldLength = c1.length;
const newLength = c2.length;
const commonLength = Math.min(oldLength, newLength);
let i;
// Patch the common area.
for (i = 0; i < commonLength; i++) {
const nextChild = (c2[i] = optimized
? cloneIfMounted(c2[i])
: normalizeVNode(c2[i]));
patch(c1[i], nextChild, container, null, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized);
}
if (oldLength > newLength) {
// remove old
unmountChildren(c1, parentComponent, parentSuspense, true, false, commonLength);
}
else {
// mount new
mountChildren(c2, container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized, commonLength);
}
};
3. 有key元素的diff算法
基本思路如下：
对于两个子VNode数组oldChildren，newChildren：
- 从头部
i=0开始，一直向后匹配，直到二者vnode不相同（或到达尾部）；（Vue3以key和Vnode.type都相同标记为二者相同） - 从二者各自尾部
e1=oldChildren.length-1和e2=newChildren.length-1开始，一直向前匹配，直到二者vnode不同（或遇到头部指针i）； - 此时，存在三种情况：
- ① newChildren 在 oldChildren的基础上，前或后增加了若干元素(
e.g. oc = [1,2,3]; nc = [1,2,3,4,5])：i > e1 && i <= e2 - ② newChildren 在 oldChildren的基础上，前或后删除了若干元素(
e.g. oc = [1,2,3,4,5]; nc = [1,2,3])：i <= e1 && i > e2 - ③ newChildren、oldChildren在执行了前后比对之后，二者中间都剩余了部分元素(
e.g. oc = [1,2,3]; nc = [1,2,3,4,5])：i <= e1 && i <= e2
- ① newChildren 在 oldChildren的基础上，前或后增加了若干元素(
- 对于①、②两种情况，和没有key的数组比较相同，直接mount或unmount剩下的元素即可；
- 对于③情况，对二者剩余子数组oc、nc，执行最大递增子序列算法：
- ① 为nc创建一个哈希表Map，键名为子元素child的key，键值为child在children中的索引；（为了减少复杂度，方便步骤②的查询）
- ② 设置一个数组
newIndexToOldIndexMap，初始化各元素为-1（Vue3中为0，oc中newIndex向后移动了1），记录nc各元素在oc中的位置：newIndexToOldIndexMap[i] = k代表nc中i位置元素，在oc中位置为k； - ③ 从头到尾遍历oc，对于它的子元素oldChild，找到它在新数组nc中的位置newIndex：
- 如果有key，从Map中查找key对应的index为newIndex，找不到则为undefined；
- 如果没有key，遍历nc，比较元素是否相同，相同则记录下它的index作为newIndex，找不到则为undefined。
- 如果newIndex为undefined，说明新子元素nc中没有这个旧元素，直接删除(unmount)当前的旧元素；
- 如果newIndex不是undefined：
- 记录它当前在oc中的位置
newIndexToOldIndexMap[newIndex] = i; - 因为nc中元素为升序排列，如果相对位置在oc中没变，那么它们在newIndexToOldIndexMap也应该是升序，因此newIndex应该是递增的：
- 记录当前已遍历的newIndex的最大值maxNewIndex，如果
newIndex >= maxNewIndex，则更新maxNewIndex; - 如果
newIndex < maxNewIndex，因为newIndex也不是undefined，则说明当前的元素移动了位置，记录下这个情况(moved = true，代表nc整体存在元素移动情况)； - patch新、旧这两个元素;
- 记录当前已遍历的newIndex的最大值maxNewIndex，如果
- 记录它当前在oc中的位置
- ④ 寻找newIndexToOldIndexMap的最大递增子序列maxSequence，它内部含有的元素，都只需要内部更新，不需要移动；
- ⑤ 从后到前遍历nc：
- 对于nc最后一个元素，它mount到容器的下方。对于非最后一个元素，它的anchor是前一个元素
[i+1]对应的DOM元素； - 如果
newIndexToOldIndexMap[i] === -1，则说明oc中没有这个新元素，将它按照anchor，进行mount； - 否则，如果存在moved === true，而且i不在maxSequence中，则按照anchor，移动当前元素（当前元素已经在步骤③被patch过，现在只需要移动）。
- 对于nc最后一个元素，它mount到容器的下方。对于非最后一个元素，它的anchor是前一个元素
const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized) => {
let i = 0;
const l2 = c2.length;
let e1 = c1.length - 1; // prev ending index
let e2 = l2 - 1; // next ending index
// [Mars] : 1. Compare the head and the tail first.
// 1. sync from start
// (a b) c
// (a b) d e
while (i <= e1 && i <= e2) {
const n1 = c1[i];
const n2 = (c2[i] = optimized ?
cloneIfMounted(c2[i]) :
normalizeVNode(c2[i]));
if (isSameVNodeType(n1, n2)) { // type and key are the same.
patch(n1, n2, container, null, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized);
} else {
break;
}
i++;
}
// 2. sync from end
// a (b c)
// d e (b c)
while (i <= e1 && i <= e2) {
const n1 = c1[e1];
const n2 = (c2[e2] = optimized ?
cloneIfMounted(c2[e2]) :
normalizeVNode(c2[e2]));
if (isSameVNodeType(n1, n2)) { // type and key are the same.
patch(n1, n2, container, null, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized);
} else {
break;
}
e1--;
e2--;
}
// [Mars] : 2. Compare the head and the tail first.
// 3. common sequence + mount
// (a b)
// (a b) c
// i = 2, e1 = 1, e2 = 2
// (a b)
// c (a b)
// i = 0, e1 = -1, e2 = 0
if (i > e1) {
if (i <= e2) {
const nextPos = e2 + 1;
const anchor = nextPos < l2 ? c2[nextPos].el : parentAnchor;
while (i <= e2) {
// mount new added vnodes not contained in oldChilds.
patch(null, (c2[i] = optimized ?
cloneIfMounted(c2[i]) :
normalizeVNode(c2[i])), container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized);
i++;
}
}
}
// 4. common sequence + unmount
// (a b) c
// (a b)
// i = 2, e1 = 2, e2 = 1
// a (b c)
// (b c)
// i = 0, e1 = 0, e2 = -1
else if (i > e2) {
while (i <= e1) {
unmount(c1[i], parentComponent, parentSuspense, true);
i++;
}
}
// 5. unknown sequence
// [i ... e1 + 1]: a b [c d e] f g
// [i ... e2 + 1]: a b [e d c h] f g
// i = 2, e1 = 4, e2 = 5
else {
const s1 = i; // prev starting index
const s2 = i; // next starting index
// 5.1 build key:index map for newChildren
const keyToNewIndexMap = new Map(); // use hashMap, cause it's easy to search an index of a key.
for (i = s2; i <= e2; i++) {
const nextChild = (c2[i] = optimized ?
cloneIfMounted(c2[i]) :
normalizeVNode(c2[i]));
if (nextChild.key != null) {
if (keyToNewIndexMap.has(nextChild.key)) {
warn$1(`Duplicate keys found during update:`, JSON.stringify(nextChild.key), `Make sure keys are unique.`);
}
keyToNewIndexMap.set(nextChild.key, i);
}
}
// 5.2 loop through old children left to be patched and try to patch
// matching nodes & remove nodes that are no longer present
let j;
let patched = 0;
const toBePatched = e2 - s2 + 1;
let moved = false;
// used to track whether any node has moved
let maxNewIndexSoFar = 0;
// works as Map<newIndex, oldIndex>
// Note that oldIndex is offset by +1
// and oldIndex = 0 is a special value indicating the new node has
// no corresponding old node.
// used for determining longest stable subsequence
const newIndexToOldIndexMap = new Array(toBePatched);
for (i = 0; i < toBePatched; i++)
newIndexToOldIndexMap[i] = 0;
for (i = s1; i <= e1; i++) {
const prevChild = c1[i];
if (patched >= toBePatched) {
// all new children have been patched so this can only be a removal
unmount(prevChild, parentComponent, parentSuspense, true);
continue;
}
let newIndex;
if (prevChild.key != null) {
newIndex = keyToNewIndexMap.get(prevChild.key);
} else {
// key-less node, try to locate a key-less node of the same type
for (j = s2; j <= e2; j++) {
if (newIndexToOldIndexMap[j - s2] === 0 &&
isSameVNodeType(prevChild, c2[j])) { // type and key are the same.
newIndex = j;
break;
}
}
}
if (newIndex === undefined) {
unmount(prevChild, parentComponent, parentSuspense, true);
} else {
newIndexToOldIndexMap[newIndex - s2] = i + 1; // n:[h,c,d,e] o:[c,d,e,h] -> newIndexToOldIndexMap: [4,1,2,3]
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex;
} else {
moved = true;
}
patch(prevChild, c2[newIndex], container, null, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized);
patched++;
}
}
// 5.3 move and mount
// generate longest stable subsequence only when nodes have moved
const increasingNewIndexSequence = moved ?
getSequence(newIndexToOldIndexMap) :
EMPTY_ARR;
j = increasingNewIndexSequence.length - 1;
// looping backwards so that we can use last patched node as anchor !!!!!!★★★
for (i = toBePatched - 1; i >= 0; i--) {
const nextIndex = s2 + i;
const nextChild = c2[nextIndex];
const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAnchor;
if (newIndexToOldIndexMap[i] === 0) {
// mount new
patch(null, nextChild, container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized);
} else if (moved) {
// move if:
// There is no stable subsequence (e.g. a reverse)
// OR current node is not among the stable sequence
if (j < 0 || i !== increasingNewIndexSequence[j]) {
move(nextChild, container, anchor, 2 /* REORDER */ );
} else {
// position is matched, no movement.
j--;
}
}
}
}
};
