Vue2 剝絲抽繭 - 虛擬 dom 之移動
虛擬 dom 之更新 中我們假設了 dom 的結構沒有發生變化，完成了 dom 屬性和內容的更新。這篇文章，我們假設 dom 沒有出現增減，只是發生了移動，看一下這種情況下的更新情況。
dom 結構
虛擬 dom 之更新 中我們介紹了不管是 dom 還是虛擬 dom 都是一個 tree 結構。
我們假設每一個節點都是一個 div 節點，葉子節點都是文本節點，每個節點寫一個名字方便觀察樹的變化。
如果 dom 的位置發生了變化，爲了複用原有的 dom，我們需要雙層遍歷，找到新的 vnode 中對應的舊 vnode ，然後從舊 vnode 中拿到 dom 對象進行更新。
for(const newVNode of newVnodeTree) {
for(const oldVNode of oldVnodeTree) {
if(isSameNode(newVNode, oldVNode)) {
newVNode.elm = oldVNodo.elm // 拿到對應的 dom
update(newVNode, oldVNode)
break;
}
}
}
結合圖和代碼，B 節點和 G 節點發生了交換，如果 G 節點想複用原來的 dom 的節點，就需要遍歷 oldVnode 來找到 G 節點，找到之後需要調用 update 函數來更新 G 節點。
我們事前並不知道哪些節點位置發生了變化，所以要依次遍歷 newVNode 的所有節點去尋找對應的 OldVNode ，找到後拿到保存在 vnode 的中 dom 節點進行 update 。
update 函數需要去拿到他們各自的父節點和鄰居節點，然後進行更新，時間複雜度可能是 O(n) ，再結合外層的兩個 for 循環，整體的時間複雜度將是 update 函數非常優秀，那麼整體的時間複雜度也一定是大於
如果虛擬 dom 比較大，這個時間複雜度是我們所不能接受的。
我們需要進行一些折中，我們不追求所有 dom 都可以進行復用，我們將複用範圍縮小至同一層級的 Children 節點上，如下圖紅框所示：
代碼就可以改成下邊的樣子：
for(const newVNode of newVnodeTree) {
const oldVNodo = 從當前節點的同層節點中尋找舊vnode（newVnode）
if(oldVNodo) {
newVNode.elm = oldVNodo.elm
update(newVNode, oldVNode)
}
}
結合圖和代碼，當我們更新 G 節點的時候，在左圖中，它的同層節點也就是 A 的孩子節點是 B、C、D，沒有 G 節點，因此 G 節點進行重新生成，不進行復用。
更新 J 節點的時候，它的同層節點是 H、I、J，此時就可以找到相應的 dom 節點進行復用。
我們再考慮一下當前算法的時間複雜度。
首先肯定所有的節點都會遍歷一遍，是 O(n)，內部分爲「從同層節點中尋找節點」和「 update 節點」兩部分。
因爲同層節點是一個節點的 Children 節點，一般情況下 Children 節點個數相對於樹的整個節點個數不會很多，可以看做常數，所以從同層節點中尋找節點可以看做 O(1) 的操作。
再看 update 操作，同樣是在同一節點下的 Children 節點中進行，父節點和鄰居節點都很好拿到，因此也可以看做 O(1) 的操作。
最終 ，整體上虛擬的 dom 的更新就降爲 O(n) 了。
更新過程
代碼的話主要是接 虛擬 dom 之更新 來完善。
回憶一下 patchVnode 函數。
function patchVnode(oldVnode, vnode) {
if (oldVnode === vnode) {
return;
}
const elm = (vnode.elm = oldVnode.elm);
const oldCh = oldVnode.children;
const ch = vnode.children;
const data = vnode.data;
if (isDef(data) && isPatchable(vnode)) {
for (i = 0; i < cbs.update.length; ++i)
cbs.update[i](oldVnode, vnode);
}
if (isUndef(vnode.text)) {
if (isDef(oldCh) && isDef(ch)) {
if (oldCh !== ch) updateChildren(elm, oldCh, ch);
} else if (isDef(oldVnode.text)) {
// 更新成了空字符
nodeOps.setTextContent(elm, "");
}
} else if (oldVnode.text !== vnode.text) {
nodeOps.setTextContent(elm, vnode.text);
}
}
如果子節點存在，就調用 updateChildren 方法進行更新子節點。
function updateChildren(elm, oldCh, ch) {
for (let i = 0; i < oldCh.length; i++) {
patchVnode(oldCh[i], ch[i]);
}
}
我們之前假設 dom 節點完全沒有變化，所以就直接一一對應進行 patchVnode 。
這篇文章的話，因爲我們假設了順序可能發生變化，因此我們遍歷新的 vnode 的後需要找到對應的舊 vnode 。
function updateChildren(elm, oldCh, ch) {
for (let i = 0; i < ch.length; i++) {
for(let j = 0; j < oldCh.length; j++) {
if(sameVnode(ch[i], oldCh[j])) {
ch[i].elm = oldCh[j].elm;
patchVnode(oldCh[i], ch[j]);
break;
}
}
}
}
其中 sameVnode 判斷函數如下：
// vue 源碼中的 sameVnode 判斷的比較多，這裏我們僅簡單理解爲 key、tag 一致，並且 data 屬性還存在即可
function sameVnode(a, b) {
return (
a.key === b.key && a.tag === b.tag && isDef(a.data) === isDef(b.data)
);
}
如果我們不設置 vnode 的 key ，第一個條件 a.key === b.key 就是 undefind === undefind ，一定是 true ，這就可能導致本來能夠複用的 dom 沒有複用上，如下圖所示：
當我們遍歷 newVnode 的第 0 個節點的時候，由於 vnode 沒有設置 key ，直接和 oldVnode 的第 0 個節點匹配到了，但這兩個 vnode 其實並不能完全複用，這雖然不會影響到最終的渲染結果，但降低了渲染的性能。
一般情況下我們不設置 key 或者將 key 設置爲循環的 index 下標不會影響到最終的渲染結果，但少數特定情況下會出現非預期的結果，此時我們需要考慮是否通過添加、修改 key 來解決。
回到我們的 updateChildren 函數：
function updateChildren(elm, oldCh, ch) {
for (let i = 0; i < ch.length; i++) {
for(let j = 0; j < oldCh.length; j++) {
if(sameVnode(ch[i], oldCh[j])) {
ch[i].elm = oldCh[j].elm;
patchVnode(oldCh[i], ch[j]);
break;
}
}
}
}
假設我們設置了 key ，成功找到了對應的 vnode ，但上邊的代碼還不夠，上邊的代碼相當於只是把 dom 更新了，但是順序還沒有改變，如下圖所示，第 0 個第 2 個節點的葉子節點的 text 更新了。
但是我們當前的 vnode 結構如下：
橙色節點和黃色節點位置進行了交換，因此我們還需要添加 dom 移動的代碼。
diff 算法
這裏就需要設計一個算法，來理清什麼情況下該移動 dom ，什麼情況下不該移動 dom 。
假設原來的順序是 a、b、c、d、e，新的順序是 a、e、b、c、d。
我們開始遍歷 newVnode ，遍歷到 a ，當前只有一個，不需要考慮順序。
遍歷到 e :
newVnode 中 e 在 a 的後邊， a 對應原來的位置是 0，e 對應原來的位置是 4 ，說明原來 e 也在 a 後邊，此時無需移動。
遍歷到 b:
newVnode 中 b 此時在 a 和 e 的後邊，如果 b 不用移動，那麼 b 對應的原來的位置應該比 a、e 對應的原來的位置都要大。
但 a 對應的原來位置是 0 ，e 對應的原來的位置是 4 ，較大的位置是 4，b 對應的原來的位置是 1 小於 4，說明 b 之前在 a 或者 e 的前邊。
此時需要移動，移動到哪裏？拿到 b 的前一個節點 e ，然後接到後邊即可。
當前 dom 順序變化：
遍歷到 c ：
c 此時在 a 、e 和 b 的後邊，如果 c 不用移動，那麼 c 對應的原來的位置應該比 a、e 、b 對應的原來的位置都要大。
但 a 對應的原來位置是 0 ，e 對應的原來的位置是 4 ，b 對應的原來的位置是 1，最大的位置是 4，c 對應的原來的位置是 2 小於 4，說明 c 之前在 a 或者 e 或者 b 的前邊。
此時 c 需要移動，移動到哪裏？拿到 c 的前一個節點 b ，然後接到後邊即可。
當前 dom 順序變化：
遍歷到 d :
d 此時在 a 、e、b 和 c 的後邊，如果 d 不用移動，那麼 d 對應的原來的位置應該比 a、e 、b 、c 對應的原來的位置都要大。
但 a 對應的原來位置是 0 ，e 對應的原來的位置是 4 ，b 對應的原來的位置是 1，c 對應的原來的位置是 2，最大的位置是 4，d 對應的原來的位置是 3 < 最大位置 4 ，說明 d 之前在 a 或者 e 或者 b 或者 c 的前邊。
此時 d 需要移動，移動到哪裏？拿到 d 的前一個節點 c ，然後接到後邊即可。
當前 dom 順序變化：
可以看到此時 dom 的順序就和 new Vnode 的順序一致了。
算法總結
我們通過當前節點和前邊所有節點對應的原位置的大小來判斷它們的相對關係需不需要變化，如果變化我們就接到前一個節點的後邊（保證它們的絕對位置關係正確），最終實現了正確的排序。
算法過程如下：
保存當前已經排好序的節點列表中對應的 oldVnode 的最大位置，然後比較當前遍歷的節點對應的原來的位置和前邊的最大位置。
如果當前對應的位置大於最大位置，那就說明順序正常無需移動，然後更新排好序節點列表 dom 的最大位置。
如果當前對應的位置小於最大位置，說明當前節點位置需要移動，我們只需要接到它的前一個節點後邊即可。
對應到代碼就是下邊的樣子了：
function updateChildren(elm, oldCh, ch) {
let beforeMaxIndex = -1;
for (let i = 0; i < ch.length; i++) {
for (let j = 0; j < oldCh.length; j++) {
if (sameVnode(ch[i], oldCh[j])) {
ch[i].elm = oldCh[j].elm;
patchVnode(oldCh[j], ch[i]);
// 移動位置
if (i > beforeMaxIndex) {
// 無需移動
beforeMaxIndex = j;
} else {
const currentVnode = ch[i];
const beforeVnode = ch[i - 1];
nodeOps.insertBefore(
elm,
currentVnode.elm,
nodeOps.nextSibling(beforeVnode.elm)
);
}
break;
}
}
}
}
當然，因爲有key 的存在，我們還可以繼續優化一下代碼，將 oldCh 通過 key 映射爲一個 map ，通過 key 直接拿到 oldCh 對應的下標，這樣就不需要每次都進行一次 for 循環去遍歷 oldCh 了。
function createKeyToOldIdx(children, beginIdx, endIdx) {
let i, key;
const map = {};
for (i = beginIdx; i <= endIdx; ++i) {
key = children[i].key;
if (isDef(key)) map[key] = i;
}
return map;
}
// 沒有 key 的話還是 for 循環
function findIdxInOld(node, oldCh, start, end) {
for (let i = start; i < end; i++) {
const c = oldCh[i];
if (isDef(c) && sameVnode(node, c)) return i;
}
}
function updateChildren(elm, oldCh, ch) {
let beforeMaxIndex = -1;
let oldKeyToIdx, idxInOld;
for (let i = 0; i < ch.length; i++) {
const newVnode = ch[i];
if (isUndef(oldKeyToIdx)) // 是否已經映射過了
oldKeyToIdx = createKeyToOldIdx(oldCh, 0, oldCh.length - 1);
idxInOld = isDef(newVnode.key)
? oldKeyToIdx[newVnode.key] // 有 key 直接映射
: findIdxInOld(newVnode, oldCh, 0, oldCh.length); // 沒有 key 的情況
if (sameVnode(newVnode, oldCh[idxInOld])) {
newVnode.elm = oldCh[idxInOld].elm;
patchVnode(oldCh[idxInOld], ch[i]);
// 移動位置
if (i > beforeMaxIndex) {
// 無需移動
beforeMaxIndex = idxInOld;
} else {
const currentVnode = newVnode;
const beforeVnode = ch[i - 1];
nodeOps.insertBefore(
elm,
currentVnode.elm,
nodeOps.nextSibling(beforeVnode.elm)
);
}
}
}
測試
我們在 render 中渲染一個數組，然後點擊的時候改變數組中元素的位置：
import * as nodeOps from "./node-ops";
import modules from "./modules";
import { createPatchFunction } from "./patch";
import { createElement } from "./create-element";
import { observe } from "./observer/reactive";
import Watcher from "./observer/watcher";
const options = {
el: "#root",
data: {
list: ["a", "b", "c"],
},
render(createElement) {
const children = [];
for (const item of this.list) {
children.push(createElement("div", { key: item }, item));
}
const vnode = createElement(
"div",
{
on: {
click: () => {
console.log(1);
this.list = ["c", "b", "a"];
},
},
},
children
);
return vnode;
},
};
const _render = function () {
const vnode = options.render.call(options.data, createElement);
return vnode;
};
const __patch__ = createPatchFunction({ nodeOps, modules });
const vm = {};
vm.$el = document.querySelector(options.el);
const _update = (vnode) => {
const prevVnode = vm._vnode;
vm._vnode = vnode;
// Vue.prototype.__patch__ is injected in entry points
// based on the rendering backend used.
if (!prevVnode) {
// initial render
vm.$el = __patch__(vm.$el, vnode);
} else {
// updates
vm.$el = __patch__(prevVnode, vnode);
}
};
observe(options.data);
new Watcher(options.data, () => _update(_render()));
看一下效果：
update
dom 順序成功進行了更新。
總
這篇文章主要介紹了 diff 算法從 diff 算法，在假設 dom 節點沒有增刪的情況下對 dom 進行了移動。
Vue2 中對上邊的 diff 算法進行了進一步的優化，下篇文章繼續。
windliang 前端，生活，成長
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/0LCtOFytT4FW1c1tlRBtdA