Vue3源碼分析-完整update流程和diif算法
前言
在上一篇文章vue的首次渲染過程中提到在組件的首次渲染階段會有一個副作用渲染函數(shù)setupRenderEffect，在這個函數(shù)內(nèi)會使用響應式API Effect創(chuàng)建副作用函數(shù)componentEffect，這里只需要簡單的理解為，當組件內(nèi)的數(shù)據(jù)改動時這個由Effect包裹的componentEffect就會重新調(diào)用，在這個函數(shù)內(nèi)部會判斷當前組件是處于首次渲染還是更新，當組件內(nèi)數(shù)據(jù)發(fā)生變化時會進入到update的分支，本文要看的diff流程也就是從這里開始。
PS: 當前的
Vue版本是3.0.5。本文會忽略TELEPORT、SUSPENSE等特殊vnode類型，對于一些細微的優(yōu)化也會忽略（比如patch函數(shù)的optimized參數(shù)）。
回顧setupRenderEffect
在組件的數(shù)據(jù)發(fā)生改變時會自動觸發(fā)副作用渲染函數(shù)setupRenderEffect：
// runtime-core/src/renderer.ts
import { effect } from '@vue/reactivity'
const setupRenderEffect = (instance, initialVNode, container, ...) => {
// 在當前的組件實例上添加 update 方法，通過響應式方法 effect 創(chuàng)建
instance.update = effect(function componentEffect() {
if (!instance.isMounted) {
//...
} else {
// 非首次渲染，進入 update 階段
let { next, vnode } = instance
// 緩存一份更新后的 vnode
let originNext = next
if (next) {
// 這里需要把更新后的組件 vnode 賦值 el，因為下面第一次 渲染新的組件 vnode 時并沒有設(shè)置 el
next.el = vnode.el
updateComponentPreRender(instance, next)
} else {
// 如果沒有 next 直接指向當前 vnode
next = vnode
}
// 渲染新的組件 vnode，因為數(shù)據(jù)發(fā)生了變化
const nextTree = renderComponentRoot(instance)
// 緩存舊的組件 vnode
const preTree = instance.subTree
// 更新實例上的 subTree 為新的組件 vnode
instance.subTree = nextTree
patch(prevTree, nextTree, ..., instance)
// 更新 DOM 元素
next.el = nextTree.el
}
}, prodEffectOptions)
這里主要看update的部分（即else代碼塊）。首先會先從組件實例instance里取出next（在處理組件一節(jié)會詳細說明next存在與不存在的情況）。
組件內(nèi)的數(shù)據(jù)發(fā)生了改變，所以要生成新的組件模板的vnode節(jié)點，在渲染階段命名為subTree，然后還要保存一份舊的subTree，這樣有了新舊subTree后就可以用patch函數(shù)更新DOM。
patch函數(shù)
在進入具體的diff流程之前，我們不妨先想一下，當數(shù)據(jù)發(fā)生改變時，會有哪些變化類型？
實際上按照類型可以分為更新普通DOM元素和更新vue組件這兩種情況。下面先關(guān)注一下patch函數(shù)的邏輯。
// runtime-core/src/renderer.ts
const patch = (n1, n2, container, ...) => {
// n1 是舊節(jié)點，n2 是新節(jié)點
// 如果 n1、n2 新舊節(jié)點的類型不同，直接銷毀舊節(jié)點
if(n1 && !isSameVNodeType(n1, n2)) {
unmount(n1, parentComponent, parentSuspense, true)
n1 = null
}
const { type, ref, shapeFlag } = n2
switch(type) {
// 處理文本節(jié)點
case Text:
processText(n1, n2, container, anchor)
break
// 處理注釋
case Comment:
processCommentNode(n1, n2, container, anchor)
break
// ...
default:
// 處理 DOM 元素
if(shapeFlag & ShapeFlags.ELEMENT) {
processElement(n1, n2, container, ...)
// 處理 vue 組件
} else if (shapeFlag & ShapeFlags.COMPONENT) {
processComponent(n1, n2, container, ...)
}
// ...
}
}
最開始先判斷新舊節(jié)點的類型是否一樣，如果不一樣，可以設(shè)想某個節(jié)點從div標簽變成span標簽，最合理的方式是直接舍棄舊節(jié)點，重新掛載新的節(jié)點。
再往下會根據(jù)當前節(jié)點類型type進行特定的處理。比如文本節(jié)點執(zhí)行processText的特定處理、注釋節(jié)點執(zhí)行processCommentNode的特定處理。這樣的前置處理實際上是一個優(yōu)化，在編譯階段，vue會將模版語法編譯成渲染函數(shù)，這個時候會把第一個參數(shù)節(jié)點類型type填上，如果這個參數(shù)命中了這樣的特殊節(jié)點，會直接執(zhí)行相應的process方法。
default塊兒里才是分析的重點，即處理普通DOM元素和vue組件。
處理DOM元素
先舉一個栗子??，假設(shè)有以下一段代碼：
<template>
<div>
<button @click="add">add</button>
<p>{{ num }}</p>
</div>
</template>
<script>
import { ref } from 'vue'
export default {
setup () {
const num = ref(1)
function add() {
num.value += 1
}
return {
num,
add
}
}
}
</script>
這段代碼非常簡單，點擊add按鈕，p標簽里的num會加一。
因為p標簽是一個普通的DOM節(jié)點，所以在具體執(zhí)行patch方法時，會走處理DOM的邏輯，執(zhí)行processElement方法。
// runtime-core/src/renderer.ts
const processElement= (n1, n2, container, ...) => {
// 無舊節(jié)點，首次渲染邏輯
if (n1 === null) {
// ...
} else {
patchElement(n1, n2, ...)
}
}
我們只關(guān)心新舊節(jié)點都存在的update邏輯，所以接著看patchElement函數(shù)。
前置屬性
在具體看patchElement之前，我們需要先了解兩個前置屬性：
1. PatchFlags
在vnode中有patchFlag這樣一個字段，用來表示當前節(jié)點發(fā)生改變的類型。PatchFlags的所有枚舉類型如下所示：
// shared/src/patchFlags.ts
export const enum PatchFlags {
TEXT = 1,
CLASS = 1 << 1,
STYLE = 1 << 2,
PROPS = 1 << 3,
FULL_PROPS = 1 << 4,
HYDRATE_EVENTS = 1 << 5,
STABLE_FRAGMENT = 1 << 6,
KEYED_FRAGMENT = 1 << 7,
UNKEYED_FRAGMENT = 1 << 8,
NEED_PATCH = 1 << 9,
DYNAMIC_SLOTS = 1 << 10,
DEV_ROOT_FRAGMENT = 1 << 11,
HOISTED = -1,
BAIL = -2
}
patchFlag所有的枚舉類型都由二進制來表示，這樣做的好處是很容易對多種類型進行判斷，比如當前變化包括TEXT和CLASS。
在判斷時，只需要對想要判斷的類型進行&操作，如果大于0，說明包含此類型。
2. dynamicChildren
vue3中對靜態(tài)節(jié)點做了標記，在patch階段，不會比較靜態(tài)節(jié)點，只會比較動態(tài)節(jié)點，即dynamicChildren內(nèi)的節(jié)點。
patchElement
了解完上面兩個屬性后我們回歸主線，看一下patchElement函數(shù)：
// runtime-core/src/renderer.ts
const patchElement = (n1, n2, ...) => {
// 緩存舊的DOM節(jié)點，因為這是DOM的更新，所以舊DOM節(jié)點即 n1.el 一定存在
const el = (n2.el = n1.el!)
// 取出新節(jié)點的 patchFlag dynamicChildren 后面會進行判斷
let { patchFlag, dynamicChildren } = n2
// 保存舊節(jié)點 props
const oldProps = n1.props || {}
// 保存新節(jié)點 props
const newProps = n2.props || {}
if (patchFlag > 0) {
// 對所 props 都進行比較更新
if (patchFlag & PatchFlags.FULL_PROPS) {
patchProps(el, n2, oldProps, newProps, ...)
} else {
// 存在動態(tài) class 屬性時
if (patchFlag & PatchFlags.CLASS) {
if (oldProps.class !== newProps.class) {
hostPatchProp(el, 'class', null, newProps.class, ...)
}
}
// 存在動態(tài) style 屬性時
if (patchFlag & PatchFlags.STYLE) {
hostPatchProp(el, 'style', oldProps.style, newProps.style, ...)
}
// 針對除了 style、class 的 props
if (patchFlag & PatchFlags.PROPS) {
const propsToUpdate = n2.dynamicProps!
for (let i = 0; i < propsToUpdate.length; i++) {
const key = propsToUpdate[i]
const prev = oldProps[key]
const next = newProps[key]
if (next !== prev) {
hostPatchProp(el, key, prev, next, ...)
}
}
}
// 存在動態(tài) 文本
if (patchFlag & PatchFlags.TEXT) {
if (n1.children !== n2.children) {
hostSetElementText(el, n2.children as string)
}
}
} else if (dynamicChildren == null) {
patchProps(el, n2, oldProps, newProps, ...)
}
}
if (dynamicChildren) {
patchBlockChildren(n1.dynamicChildren!, dynamicChildren, el, ...)
} else {
patchChildren(n1, n2, el, null, ...)
}
}
對于DOM節(jié)點的更新主要是props和子節(jié)點的更新，其中利用patchFlag和dynamicChildren做了很多優(yōu)化，不會每次都對props和子節(jié)點進行全量的對比更新。
下面這兩張圖對代碼里的一些if else分支做了總結(jié)，vue3會充分利用patchFlag和dynamicChildren做優(yōu)化，如果確定只是某個局部的變動，比如STYLE改變，那么只會調(diào)用hostPatchProp并傳入對應的參數(shù)STYLE做特定的更新。
更新props
下面一一看下上圖提到的幾個函數(shù)具體做了什么：
hostPatchProphostPatchProp函數(shù)會根據(jù)參數(shù)的key執(zhí)行相應的方法，比較簡單。
// runtime-dom/src/patchProp.ts
export const patchProp = (el, key, prevValue, nextValue, ...) => {
switch (key) {
case 'class':
// 更新 class
patchClass(el, nextValue, isSVG)
break
case 'style':
// 更新 style
patchStyle(el, prevValue, nextValue)
break
default:
// ...
patchAttr(el, key, nextValue, isSVG)
}
}
這幾個方法都比較類似，最終都是調(diào)用原生的DOM API更新，其中看下patchClass方法，這個方法比較有意思的一點是，源碼中注釋寫直接對className賦值比使用setAttribute方法要快，不得不說真的細hhhh。
// runtime-dom/src/modules/class.ts
export function patchClass(el, value) {
if (value == null) {
value = ''
}
...
// directly setting className should be faster than setAttribute in theory
el.className = value
}
patchPropspatchProps就如其名了，遍歷所有屬性，全部進行更新。
// runtime-core/src/renderer.ts
const patchProps = (el, vnode, oldProps, newProps, ...) => {
if (oldProps !== newProps) {
// 遍歷 newProps 更新
for (const key in newProps) {
const next = newProps[key]
const prev = oldProps[key]
if (next !== prev) {
hostPatchProp(el, key, prev, next, ...)
}
}
if (oldProps !== EMPTY_OBJ) {
// 遍歷 oldProps
for (const key in oldProps) {
// 如果 存在某個屬性 不在 newProps 調(diào)用 hostPatchProp 移除該屬性
if (!(key in newProps)) {
hostPatchProp(el, key, oldProps[key], null,...)
}
}
}
}
}
patchBlockChildren
DOM是一顆樹，不難想到會有子節(jié)點嵌套的情況，所以這里的子節(jié)點更新是一個深度優(yōu)先遍歷的過程，即更新完當前節(jié)點后，會去更新當前節(jié)點的子節(jié)點，不過vue3在這個過程中有所優(yōu)化。具體會通過對patch的最后一個參數(shù)optimized傳參來防止不必要的渲染。這里簡單知道有這個優(yōu)化即可，全部羅列出來比較繁瑣，感興趣的同學可以詳細看看。
這個方法也比較簡單，因為在編譯的時候已經(jīng)確定了哪些是動態(tài)節(jié)點，所以直接遍歷所有的動態(tài)節(jié)點然后進行patch即可。
// runtime-core/src/renderer.ts
const patchBlockChildren = (oldChildren, newChildren, fallbackContainer, ...) => {
for (let i = 0; i < newChildren.length; i++) {
const oldVNode = oldChildren[i]
const newVNode = newChildren[i]
patch(oldVNode, newVNode, container, ...)
}
}
patchChildren
對于子節(jié)點來說，只會有三種可能，分別是：文本節(jié)點、數(shù)組和空。所以這個方法里所有的if else分支就是在考慮新舊節(jié)點可能的全部情況，并進行相應的處理。
// runtime-core/src/renderer.ts
const patchChildren = (n1, n2, container, ...) => {
const c1 = n1 && n1.children
const prevShapeFlag = n1 ? n1.shapeFlag : 0
const c2 = n2.children
const { patchFlag, shapeFlag } = n2
// ...
// children has 3 possibilities: text, array or no children.
if (prevShapeFlag & ShapeFlags.TEXT_CHILDREN) {
// text children fast path
if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
// 如果舊子節(jié)點是數(shù)組 先卸載
unmountChildren(c1, parentComponent, parentSuspense)
}
if (c2 !== c1) {
// 更新文本節(jié)點
hostSetElementText(container, c2)
}
} else {
if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
// 舊子節(jié)點是數(shù)組
if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
// two arrays, cannot assume anything, do full diff
patchKeyedChildren(c1, c2, container, ...)
} else {
// 沒有新子節(jié)點，直接卸載舊子節(jié)點
unmountChildren(c1, parentComponent, parentSuspense, true)
}
} else {
// prev children was text OR null
// new children is array OR null
if (prevShapeFlag & ShapeFlags.TEXT_CHILDREN) {
hostSetElementText(container, '')
}
// mount new if array
if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
mountChildren(c2, container, ...)
}
}
}
}
其中新舊節(jié)點都是數(shù)組的情況涉及到我們平常所說的diff算法，會放到后面專門去解析。
處理vue組件
看完處理DOM元素的情況，接下來看處理vue組件。再舉一個例子??：
<template>
<div>
<button @click="add">add</button>
<foo :num="num" />
</div>
</template>
<script>
import { ref } from 'vue'
export default {
setup () {
const num = ref(1)
function add() {
num.value += 1
}
return {
num,
add
}
}
}
</script>
// foo 組件
<template>
<div>
<p>num is, {{ num }}</p>
</div>
</template>
<script>
export default {
props: {
num: Number
}
}
</script>
這個例子就是將之前的普通元素標簽換成了foo組件，foo組件接收num props，點擊add按鈕就會加一。
讓我們回到patch方法，當點擊add按鈕時會觸發(fā)重新渲染，其中更新foo時會進入processComponent方法。
// runtime-core/src/renderer.ts
const processComponent = (n1, n2, container, ...) => {
if (n1 === null) {
// 首次渲染
// ...
} else {
// 更新
updateComponent(n1, n2, ...)
}
}
在更新的時候我們只關(guān)心updateComponent。
// runtime-core/src/renderer.ts
const updateComponent = (n1, n2, ...) => {
// 緩存最新的 組件 vnode
const instance = (n2.component = n1.component)!
// 對比新舊 vnode 節(jié)點，
if (shouldUpdateComponent(n1, n2)) {
// ...
// 把最新組件vnode 賦值給 instance.next
instance.next = n2
// in case the child component is also queued, remove it to avoid
// double updating the same child component in the same flush.
invalidateJob(instance.update)
// instance.update is the reactive effect runner.
instance.update()
} else {
// no update needed. just copy over properties
n2.component = n1.component
n2.el = n1.el
instance.vnode = n2
}
}
在updateComponent方法內(nèi)部，先緩存最新的組件實例，接下來有一個優(yōu)化點，會通過shouldUpdateComponent方法來比較新舊組件是否需要更新，這里主要是對比組件vnode的props、children等屬性。這樣的提前判斷會避免不必要的渲染，如果需要渲染，會把最新的組件vnode賦值給instance.next，這在下面調(diào)用組件首次渲染時注冊的instance.update副作用渲染函數(shù)時會使用到。
至于invalidateJob這個方法，它是從scheduler.ts文件中引出的，所以大概可以知道是處理調(diào)度相關(guān)。再結(jié)合注釋和傳入的參數(shù)，就比較明白了。DOM結(jié)構(gòu)是一棵樹，從上面的流程中可以知道，在更新一個節(jié)點時不光會更新節(jié)點本身，還會更新節(jié)點的子節(jié)點，所以，vue會在這里進行檢查，看是否當前組件的副作用函數(shù)已經(jīng)在隊列中了，如果在，直接移除掉，反正再往下也會主動觸發(fā)更新。這樣就避免了二次重復渲染。
如果對比了新舊節(jié)點發(fā)現(xiàn)不需要更新，那很好辦，就不會主動調(diào)用instance.update觸發(fā)更新，僅僅是更新相關(guān)的屬性。
接著執(zhí)行instance.update，這個函數(shù)就是在setupRenderEffect內(nèi)創(chuàng)建的。最終子組件的更新還會走一遍自己副作用渲染函數(shù)，然后patch子組件的子模板DOM，接上上面的流程。
update流程小結(jié)
其實到這里可能還是不太清楚整個流程是怎樣的，還是以上面的例子為代表，我們從頭捋一遍點擊add后到底經(jīng)歷了哪些流程。首先我們有一個根組件app，app模板的根DOM元素是div，div里面有button元素和foo組件。app與foo之間通過props: num通信，點擊button時num會加一。
當點擊add后，app組件內(nèi)的num更新，由于初次渲染時在組件實例上添加了響應式的update方法。app組件會觸發(fā)自身的update。
// runtime-core/src/renderer.ts
// setupRenderEffect 函數(shù)內(nèi)
instance.update = effect(function componentEffect() {
if (!instance.isMounted) {
...
} else {
let { next } = instance
if (next) {
updateComponentPreRender(instance, next)
} else {
next = vnode
}
const nextTree = renderComponentRoot(instance)
const prevTree = instance.subTree
instance.subTree = nextTree
patch(prevTree, nextTree, ..., instance)
}
}, prodEffectOptions)
注意現(xiàn)在是app組件自身的數(shù)據(jù)變化，所以此時是沒有next的，接下來渲染新的子組件vnode，得到真實的模版vnode nextTree，用新舊subTree進行patch。
因為對比的是app內(nèi)模板的普通元素vnode，此時patch的元素類型是div，進入更新普通元素的流程，先更新props，再更新子節(jié)點，當前div下的子節(jié)點有button和foo組件，先更新button元素，再更新foo組件。
在更新foo組件時，會先將foo組件instance.next賦值為最新的foo子組件vnode，之后再主動調(diào)用foo.update進入上面的副作用渲染函數(shù)，這次的實例是foo組件且next存在值。之后就是同樣的邏輯，進入foo組件的patch，后面就省略掉不細說了。
可以發(fā)現(xiàn)，一個組件的更新存在兩種情況。在副作用渲染函數(shù)的內(nèi)部，如果next不存在，是組件本身數(shù)據(jù)發(fā)生變化引發(fā)的update，next存在，是父組件更新子組件的時候引發(fā)的update。
diff算法
在前面分析更新普通元素子節(jié)點時，有一種情況是新舊子節(jié)點都是數(shù)組，這個時候就需要某種成本較低的策略進行diff更新。
先假設(shè)所有元素都擁有一個獨一無二的
key值。
我們可以先想一下，新舊子節(jié)點都是數(shù)組會有哪幾種變化情況？
無論是哪種變化最后都是由更新、添加、刪除、移動這四種操作的一種或者幾種的組合。
源碼里面劃分的比較清晰，主要分為了三種情況：在同一位置添加一個或多個節(jié)點、在同一位置刪除一個或多個節(jié)點和處理未知序列。
從上面這三種情況可以看出一個共性，從頭開始的一部分和從尾部倒序的一部分（所有淡黃色的）可能是不需要改變的，不論哪種情況整體都可以分為從頭部正序不需要改動的部分、中間發(fā)生變動的部分、從尾部倒序不需要改動的部分。所以在最開始，可以先進行頭部和尾部的預處理。
源碼里在diff算法的最開始，會先從頭部正序掃描和從尾部倒序掃描，以便排除類型一樣的干擾項，進一步的提高效率。
此處的類型一樣指
vnode節(jié)點的type、key都一樣。
// runtime-core/src/renderer.ts
const patchKeyedChildren = (c1, c2, ...) => {
// 從頭部開始掃描的索引
let i = 0
// 新節(jié)點長度
const l2 = c2.length
// 舊數(shù)組序列尾部索引
let e1 = c1.length - 1
// 新數(shù)組序列尾部索引
let e2 = l2 - 1
// 1. 正序掃描頭部，找到不相同的為止
while (i <= e1 && i <= e2) {
// 當前掃描到的舊數(shù)組序列中的節(jié)點
const n1 = c1[i]
// 當前掃描到的新數(shù)組序列中的節(jié)點
const n2 = c2[i]
// 如果當前的新舊節(jié)點 type、key 相同，才為 true
if (isSameVNodeType(n1, n2)) {
// 更新
patch(n1, n2, ...)
} else {
break
}
i++
}
// 2. 倒序掃描尾部，找到不相同的為止
while (i <= e1 && i<= e2) {
// 當前掃描到的舊數(shù)組序列中的節(jié)點
const n1 = c1[e1]
// 當前掃描到的新數(shù)組序列中的節(jié)點
const n2 = c2[e2]
if (isSameVNodeType(n1, n2)) {
patch(n1, n2, ...)
} else {
break
}
e1--
e2--
}
// ...
}
這段代碼就像上面說到的那樣，先從頭部正序掃描，再從尾部倒序掃描，終止的條件是當前索引不能越界或者遇到新舊數(shù)組序列中的節(jié)點，類型不一樣或者key值不一樣，掃描到相同的節(jié)點會進行patch更新，這里不用操心當前的節(jié)點到底是否需要更新，patch函數(shù)內(nèi)部會做相關(guān)的判斷。
同一位置的添加、刪除
這種情況相對而言比較簡單，因為只涉及到添加或者刪除這兩種單一的原子操作之一，且位置還都是固定。
只需要掃描頭部尾部，找出是在哪個位置進行的添加或刪除，之后再進行相應的操作即可。
添加節(jié)點使用這個例子，從頭部和從尾部掃描完畢之后，各個變量情況如圖所示。
// runtime-core/src/renderer.ts
const patchKeyedChildren = (c1, c2, ...) => {
// ...
// 1. 正序掃描頭部，找到不相同的為止
// 2. 倒序掃描尾部，找到不相同的為止
// 3. if (同一位置添加節(jié)點)
if (i > e1) {
if (i <= e2) {
const nextPos = e2 + 1
const anchor = nextPos < l2 ? (c2[nextPos].el : parentAnchor
while (i <= e2) {
// 第一個參數(shù) 舊節(jié)點 為 null，新的掛載節(jié)點
patch(null, c2[i], ...)
i++
}
}
}
// ...
}
如果i > e1 && i <= e2，第一個條件語句表示當前索引已經(jīng)到了舊數(shù)組序列除去尾部相同節(jié)點的末尾，但是還沒到新數(shù)組序列除去尾部相同節(jié)點的末尾，意味著新的數(shù)組序列在舊的數(shù)組序列上新添加了一個或多個的連續(xù)節(jié)點，所以自然而然會命中新添加節(jié)點的情況。只需要對[i, e2]這個新數(shù)組序列內(nèi)的節(jié)點依次進行掛載即可。
當然，如果掃描完畢后情況相反，即當前索引到了新數(shù)組序列除去尾部相同節(jié)點的末尾，但是還沒到舊數(shù)組序列除去尾部相同節(jié)點的末尾，即發(fā)生變化的索引區(qū)間新數(shù)組序列小于舊數(shù)組序列的，這意味著新數(shù)組序列在舊數(shù)組序列的基礎(chǔ)上刪除了一個或多個節(jié)點。只需要對[i, e2]這個舊數(shù)組序列內(nèi)的節(jié)點依次進行卸載即可。
// runtime-core/src/renderer.ts
const patchKeyedChildren = (c1, c2, ...) => {
// ...
// 1. 正序掃描頭部，找到不相同的為止
// 2. 倒序掃描尾部，找到不相同的為止
// 3. if (同一位置添加節(jié)點) 沒有命中
// 4. else if (同一位置刪除節(jié)點)
else if (i > e2) {
if (i <= e1) {
while (i <= e1) {
unmount(c1[i], ...)
i++
}
}
}
// ...
}
未知數(shù)組序列
如果沒有命中上面的兩種情況，那么就需要處理未知數(shù)組序列了?？匆幌孪旅孢@個例子。
先人工分析一下，中間發(fā)生變動的部分經(jīng)過了哪些改變：
有節(jié)點的移動， d節(jié)點移動到c節(jié)點前，e節(jié)點移動到d節(jié)點前。有節(jié)點的添加，添加了 h節(jié)點。
按照之前的流程，仍舊是先進行頭部與尾部的預處理掃描，通過i、e1、e2圈出發(fā)生改動的區(qū)間。這個例子不符合添加和刪除的分支，所以進入最后一個elsec處理未知序列的代碼塊 。
// runtime-core/src/renderer.ts
const patchKeyedChildren = (c1, c2, ...) => {
// ...
// 1. 正序掃描頭部，找到不相同的為止
// 2. 倒序掃描尾部，找到不相同的為止
// 3. if (同一位置添加節(jié)點) 沒有命中
// 4. else if (同一位置刪除節(jié)點) 沒有命中
// 5. else 處理未知數(shù)組序列
else {
// 舊數(shù)組未知序列開始索引
const s1 = i
// 新數(shù)組未知序列開始索引
const s2 = i
// 5.1 創(chuàng)建新數(shù)組未知序列的 key -> 索引 map
const keyToNewIndexMap = new Map()
// 因為針對新數(shù)組未知序列創(chuàng)建 map，所以臨界是 e2
for (i = s2; i <= e2; i++) {
// 遍歷到的新數(shù)組的節(jié)點
const nextChild = c2[i]
// 前面已經(jīng)假設(shè)一定存在 key 值
if (nextChild.key !== null) {
// 存儲的 <key, value> 是 節(jié)點 key 值、索引
keyToNewIndexMap.set(nextChild.key, i)
}
}
// ...
}
// ...
}
注釋5開始現(xiàn)在正式進入到處理未知序列的流程中，會根據(jù)新數(shù)組的未知序列建立一個keyToNewIndexMap<key, index>的map結(jié)構(gòu)。只需要遍歷新數(shù)組的未知序列即可，得到{ e: 2, d: 3, c: 4, h: 5 }。
遍歷舊數(shù)組序列進行選擇性的更新和移除
下面我們遍歷舊數(shù)組的未知序列，根據(jù)key值且對照著剛剛建立的keyToNewIndexMap，查找舊數(shù)組序列中哪些節(jié)點仍然存在可以patch、哪些節(jié)點不存在需要移除、哪些節(jié)點需要移動。
// runtime-core/src/renderer.ts
const patchKeyedChildren = (c1, c2, ...) => {
// ...
// 1. 正序掃描頭部，找到不相同的為止
// 2. 倒序掃描尾部，找到不相同的為止
// 3. if (同一位置添加節(jié)點) 沒有命中
// 4. else if (同一位置刪除節(jié)點) 沒有命中
// 5. else 處理未知數(shù)組序列
else {
// 舊數(shù)組未知序列開始索引
const s1 = i
// 新數(shù)組未知序列開始索引
const s2 = i
// 5.1 創(chuàng)建新數(shù)組未知序列的 key -> 索引 map
// 5.2 遍歷舊數(shù)組未知序列，使用 key 值，根據(jù)keyToNewIndexMap 找出哪些節(jié)點需要patch、移除、移動
// 新舊數(shù)組中已經(jīng) patch 過的節(jié)點數(shù)
let patched = 0
// 所有待處理的節(jié)點，是新數(shù)組未知序列的長度
const toBePatched = e2 - s2 + 1
// 是否有節(jié)點需要移動
let moved = false
// used to track whether any node has moved 跟蹤是否有節(jié)點移動
let maxNewIndexSoFar = 0
// 這個數(shù)組本身的 index 代表新數(shù)組元素的索引，數(shù)組的值代表舊數(shù)組元素的索引
const newIndexToOldIndexMap = new Array(toBePatched)
// 初始化數(shù)組值為 0
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
// 遍歷舊數(shù)組未知序列
for (i = s1; i <= e1; i++) {
// 當前的 舊節(jié)點
const prevChild = c1[i]
// 如果已經(jīng) patch 過的舊節(jié)點數(shù)大于等于 所有新數(shù)組中待處理的節(jié)點
// 說明所有新數(shù)組中的節(jié)點都已經(jīng) patch 完畢，其余的要移除
if (patched >= toBePatched) {
unmount(prevChild, ...)
continue
}
let newIndex
// 假設(shè) key 一定存在
if (prevChild.key != null) {
// 從 keyToNewIndexMap 中獲取當前節(jié)點在新數(shù)組中的索引
newIndex = keyToNewIndexMap.get(prevChild.key)
}
// 如果當前節(jié)點在新數(shù)組中找不到，說明新數(shù)組中沒有，移除該節(jié)點
if (newIndex === undefined) {
unmount(prevChild, ...)
} else {
// 更新數(shù)組，因為默認值是 0，i 有可能是 0，+ 1 避免和默認值沖突
newIndexToOldIndexMap[newIndex - s2] = i + 1
// maxNewIndexSoFar 初始值是0
// 每次maxNewIndexSoFar賦值的是當前節(jié)點在 新數(shù)組中的索引
// 如果新數(shù)組的順序和舊數(shù)組一樣，那么就是遞增的
// false 說明順序發(fā)生改變
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex
} else {
moved = true
}
// patch 新舊節(jié)點中匹配的節(jié)點
patch(prevChild. c2[newIndex], ...)
// 當前 patch 過的節(jié)點數(shù) +1
pached++
}
}
}
// ...
}
因為現(xiàn)在的DOM還是由舊數(shù)組生成的，我們需要知道當前的這些舊DOM節(jié)點是需要更新還是刪除還是移動。所以我們要去遍歷舊數(shù)組的未知序列，并結(jié)合剛生成的keyToNewIndexMap與新數(shù)組的未知序列進行對比。
先定義了幾個變量。patched表示當前已經(jīng)更新的節(jié)點數(shù)，toBePatched表示當前待更新的全部節(jié)點，通過這個描述我們也就知道了，如果patched大于等于toBePatched，那么剩下的舊節(jié)點就是要全部舍棄的。
moved用來表示當前是否有移動的節(jié)點。
maxNewIndexSoFar用來判斷是否有節(jié)點移動。
newIndexToOldIndexMap這個數(shù)組本身的index代表當前節(jié)點在新數(shù)組序列中的索引，實際的值代表當前節(jié)點舊子序列索引。默認值全部是0。
接下來開始正式遍歷舊數(shù)組，先取出舊數(shù)組序列里的節(jié)點c1[i]，然后判斷patched是否大于等于toBePatched，如果是，卸載當前的舊節(jié)點，跳出本次循環(huán)。
如果當前更新的節(jié)點數(shù)沒有大于等于所有待更新的節(jié)點數(shù)，那么開始更新keyToNewIndexMap這個數(shù)組，只需要通過key值從newIndexToOldIndexMap內(nèi)取出相應的newIndex索引即可。
如果找不到索引，說明在新的數(shù)組序列中這個節(jié)點不存在，直接刪除此節(jié)點。
如果找到了這個索引，那么更新newIndexToOldIndexMap[newIndex - s2] = i + 1，這里為什么要i+1呢？因為這個數(shù)組的默認值設(shè)置為了0，如果當前的i就是0，會引起沖突。
再往下執(zhí)行，因為maxNewIndexSoFar 初始值是0，每次maxNewIndexSoFar賦值的是當前節(jié)點在新數(shù)組中的索引，如果新數(shù)組的順序和舊數(shù)組一樣，那么每次的maxNewIndexSoFar不可能大于newIndex。如果大于了，說明有節(jié)點發(fā)生了移動，需要將moved設(shè)置為true。
最后，沒有經(jīng)過前面的刪除，證明當前的這個節(jié)點在新舊節(jié)點中都是存在的，那么直接patch(prevChild, c2[newIndex])即可。最后別忘記把記錄已更新節(jié)點數(shù)變量patched加一。
移動和掛載新節(jié)點
通過moved變量，我們已經(jīng)知道了當前有節(jié)點移動，下面需要處理的就是移動和掛載新節(jié)點。
vue3移動節(jié)點采取的策略是先得到最長遞增子序列的索引newIndexToOldIndexMap。舉個列子：
[2, 3, 1, 0]的最長遞增子序列是[2, 3]，最終需要的索引是[0, 1]
關(guān)于如何求解最長遞增子序列，推薦看leetcode300最長遞增子序列題解，在這里就不贅述具體算法實現(xiàn)了，主要目標仍然是在整體流程。
// runtime-core/src/renderer.ts
const patchKeyedChildren = (c1, c2, ...) => {
// ...
// 1. 正序掃描頭部，找到不相同的為止
// 2. 倒序掃描尾部，找到不相同的為止
// 3. if (同一位置添加節(jié)點) 沒有命中
// 4. else if (同一位置刪除節(jié)點) 沒有命中
// 5. else 處理未知數(shù)組序列
else {
// 5.1 創(chuàng)建新數(shù)組未知序列的 key -> 索引 map
// 5.2 遍歷舊數(shù)組未知序列，使用 key 值，根據(jù)keyToNewIndexMap 找出哪些節(jié)點需要patch、移除、移動
// 5.3 移動和掛載新節(jié)點
// 如果有節(jié)點移動，得到 newIndexToOldIndexMap 的最長遞增子序列的索引
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: EMPTY_ARR
// 用于節(jié)點移動判斷
let j = increasingNewIndexSequence.length - 1
// 倒序新數(shù)組的未知序列，因為插入節(jié)點時使用 insertBefore 即向前插，倒序遍歷可以使用上一個更新的節(jié)點作為錨點
for (i = toBePatched - 1; i >= 0; i--) {
// 當前在整個新數(shù)組中，未知序列的索引，s2 是頭部相同節(jié)點的偏移量
const nextIndex = s2 + i
// 當前在整個新數(shù)組中，未知序列的節(jié)點
const nextChild = c2[nextIndex]
// 當前節(jié)點的下一個節(jié)點，如果當前節(jié)點是最后一個節(jié)點，那么取整個父節(jié)點的下一個節(jié)點作為插入點
const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1] : parentAnchor
// 如果仍然是默認值 0 證明是一個全新的節(jié)點
if (newIndexToOldIndexMap[i] === 0) {
// 掛載新的節(jié)點
patch(null, nextChild, container, anchor, ...)
// 存在節(jié)點移動
} else if (moved) {
// 當前索引不是最長遞增子序列里的值，需要移動
if (j < 0 || i !== increasingNewIndexSequence[j]) {
move(nextChild, container, anchor)
// 當前索引是最長遞增子序列里的值，j 指向下一個
} else {
j--
}
}
}
}
// ...
}
在得到最長遞增子序列索引后，設(shè)置一個變量j，它的初始值是最長遞增子序列索引的length - 1，即指向其末尾，主要是用來判斷節(jié)點是否需要移動。
下面會倒序遍歷新數(shù)組的未知序列，因為無論是在patch中還是下面移動節(jié)點的move方法，其插入節(jié)點的操作都是使用insertBefore向前插入。在每一次倒序遍歷的時候，如果需要的話我們可以很輕松的選取上一次已經(jīng)處理完畢的節(jié)點作為基準，把當前節(jié)點，插入到它的前面。
進入到每一輪的遍歷，其實會出現(xiàn)三種情況：
使用
newIndexToOldIndexMap用當前的新數(shù)組索引查找舊數(shù)組索引，發(fā)現(xiàn)是初始值0，表示舊數(shù)組中沒有這個節(jié)點，那么使用patch方法掛載一個新的節(jié)點即可。當前的索引不在最長遞增子序列中（
j < 0會越界，所以提前可以確定不存在），說明當前節(jié)點需要移動，那么調(diào)用move(nextChild, container, anchor)即可。當前的索引恰好是最長遞增子序列的值，說明該節(jié)點不需要移動，維護
j變量。
到這兒，完成了對于未知序列的更新就完成了，下面看一下當前這個例子的具體執(zhí)行過程。
沒有key值的情況
上面的流程一直在假設(shè)每一個節(jié)點都有一個獨一無二的key值，如果我們不寫key值會怎樣呢？
因為一般數(shù)組渲染都會使用
v-for，所以在這里這個沒有key值的情況指所有的新舊數(shù)組節(jié)點都沒有key，而非有的節(jié)點存在key，有的節(jié)點不存在key。
如果沒有寫key值，在patchChildren函數(shù)內(nèi)，會根據(jù)patchFlag進入patchUnkeyedChildren這個函數(shù)內(nèi)。
// runtime-core/src/renderer.ts
const patchChildren = (n1, n2, ...) => {
// ...
if (patchFlag & PatchFlags.KEYED_FRAGMENT) {
patchKeyedChildren(...)
return
} else if (patchFlag & PatchFlags.UNKEYED_FRAGMENT) {
// 無 key 值的情況
patchUnkeyedChildren(...)
return
}
// ...
}
其實對于不寫key值的diff處理非常的簡單粗暴，會先取新舊數(shù)組長度較小的作為公共長度，然后以這個較小的長度挨個進行遍歷并對新舊數(shù)組的節(jié)點patch。
之后判斷：
如果新數(shù)組的長度大于舊數(shù)組，說明有新增的節(jié)點，那么只需要接著掛載即可。 如果新數(shù)組的長度小于舊數(shù)組，說明有刪除的節(jié)點，那么只需要從尾部開始刪除即可。
// runtime-core/src/renderer.ts
const patchUnkeyedChildren = (c1, c2, ...) => {
c1 = c1 || EMPTY_ARR
c2 = c2 || EMPTY_ARR
const oldLength = c1.length
const newLength = c2.length
// 選取較小長度作為公共部分
const commonLength = Math.min(oldLength, newLength)
// 依次 patch
for (let i = 0; i < commonLength; i++) {
const nextChild = c2[i]
patch(c1[i], nextChild, ...)
}
if (oldLength > newLength) {
// remove old
unmountChildren(...)
} else {
// mount new
mountChildren(...)
}
}
舉個例子??：
我們可以很明顯的看出這種情況的不足：沒有利用任何一個舊節(jié)點，全部進行無腦的patch更新。
最后
到此，你已經(jīng)看完了vue3更新時的整個流程和完整的diff算法～如果有收獲的話，點個贊支持一下吧～
參考資料
https://github.com/vuejs/vue-next/blob/master/packages/runtime-core/src/renderer.ts
https://juejin.cn/post/6919376064833667080
