組件更新：完整的 DOM diff 流程

• 組件渲染過程，就是把各種類型的vnode渲染成真是DOM
• 組件是由模板、組件描述對象和數(shù)據(jù)構(gòu)成的
• 數(shù)據(jù)的變化會影響組件的變化
• 組件的渲染過程中創(chuàng)建了一個帶副作用的渲染函數(shù)，當(dāng)數(shù)據(jù)變化的時候就會執(zhí)行這個渲染函數(shù)來觸發(fā)組件的更新

副作用渲染函數(shù)更新組件的過程

• 帶副作用渲染函數(shù) setupRenderEffect 的實現(xiàn)

const setupRenderEffect = (instance, initialVNode, container, anchor, parentSuspense, isSVG, optimized) => {
  // 創(chuàng)建響應(yīng)式的副作用渲染函數(shù)
  instance.update = effect(function componentEffect() {
    if (!instance.isMounted) {
      // 渲染組件
    }
    else {
      // 更新組件
      let { next, vnode } = instance
      // next 表示新的組件 vnode
      if (next) {
        // 更新組件 vnode 節(jié)點信息
        updateComponentPreRender(instance, next, optimized)
      }
      else {
        next = vnode
      }
      // 渲染新的子樹 vnode
      const nextTree = renderComponentRoot(instance)
      // 緩存舊的子樹 vnode
      const prevTree = instance.subTree
      // 更新子樹 vnode
      instance.subTree = nextTree
      // 組件更新核心邏輯，根據(jù)新舊子樹 vnode 做 patch
      patch(prevTree, nextTree,
        // 如果在 teleport 組件中父節(jié)點可能已經(jīng)改變，所以容器直接找舊樹 DOM 元素的父節(jié)點
        hostParentNode(prevTree.el),
        // 參考節(jié)點在 fragment 的情況可能改變，所以直接找舊樹 DOM 元素的下一個節(jié)點
        getNextHostNode(prevTree),
        instance,
        parentSuspense,
        isSVG)
      // 緩存更新后的 DOM 節(jié)點
      next.el = nextTree.el
    }
  }, prodEffectOptions)
}

• 主要做了三件事
• 1、更新組件 vnode 節(jié)點
  • 判斷組件實例中是否有新的組件 vnode（用 next 表示）
  • 有則更新組件 vnode，
  • 沒有則next 指向之前的組件 vnode
• 2、渲染新的子樹 vnode
  • 根據(jù)最新數(shù)據(jù)進(jìn)行渲染
• 3、根據(jù)新舊子樹 vnode 執(zhí)行 patch 邏輯
  • 用來找出新舊子樹vnode的不同，并找到一種合適的方式更新 DOM

核心邏輯：patch 流程

const patch = (n1, n2, container, anchor = null, parentComponent = null, parentSuspense = null, isSVG = false, optimized = false) => {
  // 如果存在新舊節(jié)點, 且新舊節(jié)點類型不同，則銷毀舊節(jié)點
  if (n1 && !isSameVNodeType(n1, n2)) {
    anchor = getNextHostNode(n1)
    unmount(n1, parentComponent, parentSuspense, true)
    // n1 設(shè)置為 null 保證后續(xù)都走 mount 邏輯
    n1 = null
  }
  const { type, shapeFlag } = n2
  switch (type) {
    case Text:
      // 處理文本節(jié)點
      break
    case Comment:
      // 處理注釋節(jié)點
      break
    case Static:
      // 處理靜態(tài)節(jié)點
      break
    case Fragment:
      // 處理 Fragment 元素
      break
    default:
      if (shapeFlag & 1 /* ELEMENT */) {
        // 處理普通 DOM 元素
        processElement(n1, n2, container, anchor, parentComponent, parentSuspense, isSVG, optimized)
      }
      else if (shapeFlag & 6 /* COMPONENT */) {
        // 處理組件
        processComponent(n1, n2, container, anchor, parentComponent, parentSuspense, isSVG, optimized)
      }
      else if (shapeFlag & 64 /* TELEPORT */) {
        // 處理 TELEPORT
      }
      else if (shapeFlag & 128 /* SUSPENSE */) {
        // 處理 SUSPENSE
      }
  }
}
function isSameVNodeType (n1, n2) {
  // n1 和 n2 節(jié)點的 type 和 key 都相同，才是相同節(jié)點
  return n1.type === n2.type && n1.key === n2.key
}

• 首先判斷新舊節(jié)點是否是相同的vnode類型
  • 如果不同，那么最簡單的操作就是刪除舊的 div 節(jié)點，再去掛載新的 ul 節(jié)點
  • 如果是相同的 vnode 類型，就需要走 diff 更新流程了

處理組件

更新過程也是一個樹的深度優(yōu)先遍歷過程，當(dāng)前要更新的vnode為組件類型，執(zhí)行processComponent處理

const processComponent = (n1, n2, container, anchor, parentComponent, parentSuspense, isSVG, optimized) => {
  if (n1 == null) {
    // 掛載組件
  }
  else {
    // 更新子組件
    updateComponent(n1, n2, parentComponent, optimized)
  }
}
const updateComponent = (n1, n2, parentComponent, optimized) => {
  const instance = (n2.component = n1.component)
  // 根據(jù)新舊子組件 vnode 判斷是否需要更新子組件
  if (shouldUpdateComponent(n1, n2, parentComponent, optimized)) {
    // 新的子組件 vnode 賦值給 instance.next
    instance.next = n2
    // 子組件也可能因為數(shù)據(jù)變化被添加到更新隊列里了，移除它們防止對一個子組件重復(fù)更新
    invalidateJob(instance.update)
    // 執(zhí)行子組件的副作用渲染函數(shù)
    instance.update()
  }
  else {
    // 不需要更新，只復(fù)制屬性
    n2.component = n1.component
    n2.el = n1.el
  }
}

• 通過updateComponent方法更新子組件
• 先通過shouldUpdateComponent，根據(jù)新舊子組件vnode來判斷是否需要更新子組件，主要是通過檢測和對比組件 vnode 中的 props、chidren、dirs、transiton 等屬性，來決定子組件是否需要更新
• 注意，組件的數(shù)據(jù)變化只會影響當(dāng)前組件的更新，也會檢查子組件是否需要更新，并通過某種機(jī)制避免子組件重復(fù)更新。
• 如果組件需要更新
  • 執(zhí)行invalidateJob（instance.update），避免子組件由于自身數(shù)據(jù)變化導(dǎo)致的重復(fù)更新
  • 然后又執(zhí)行了子組件的副作用渲染函數(shù)instance.update來主動觸發(fā)子組件的更新。
• 結(jié)合副作用渲染函數(shù)，如何更新組件

...
// 更新組件
let { next, vnode } = instance
// next 表示新的組件 vnode
if (next) {
  // 更新組件 vnode 節(jié)點信息
  updateComponentPreRender(instance, next, optimized)
}
else {
  next = vnode
}
const updateComponentPreRender = (instance, nextVNode, optimized) => {
  // 新組件 vnode 的 component 屬性指向組件實例
  nextVNode.component = instance
  // 舊組件 vnode 的 props 屬性
  const prevProps = instance.vnode.props
  // 組件實例的 vnode 屬性指向新的組件 vnode
  instance.vnode = nextVNode
  // 清空 next 屬性，為了下一次重新渲染準(zhǔn)備
  instance.next = null
  // 更新 props
  updateProps(instance, nextVNode.props, prevProps, optimized)
  // 更新 插槽
  updateSlots(instance, nextVNode.children)
}
...

• 我們在更新組件的DOM前，需要先更新組件vnode節(jié)點信息
  • 包括更改組件實例的vnode指針
  • 更新props和更新插槽等一系列操作
• 因為組件在稍后執(zhí)行renderComponentRoot時會重新渲染新的子樹vnode，它依賴了更新后的組件vnode中的 props 和 slots 等數(shù)據(jù)

一個組件重新渲染可能會有兩種場景

• 1、組件本身的數(shù)據(jù)變化，這種情況下 next 是 null
• 2、父組件在更新的過程中，遇到子組件節(jié)點，先判斷子組件是否需要更新，如果需要則主動執(zhí)行子組件的重新渲染方法，這種情況下 next 就是新的子組件 vnode

processComponent 的本質(zhì)

• 判斷子組件是否需要更新
• 如果需要則遞歸執(zhí)行子組件的副作用渲染函數(shù)來更新
• 否則僅僅更新一些 vnode 的屬性，并讓子組件實例保留對組件 vnode 的引用
• 用于子組件自身數(shù)據(jù)變化引起組件重新渲染的時候，在渲染函數(shù)內(nèi)部可以拿到新的組件 vnode

處理普通元素類型

當(dāng)前要更新的vnode為普通元素，則執(zhí)行processElement

const processElement = (n1, n2, container, anchor, parentComponent, parentSuspense, isSVG, optimized) => {
  isSVG = isSVG || n2.type === 'svg'
  if (n1 == null) {
    // 掛載元素
  }
  else {
    // 更新元素
    patchElement(n1, n2, parentComponent, parentSuspense, isSVG, optimized)
  }
}
const patchElement = (n1, n2, parentComponent, parentSuspense, isSVG, optimized) => {
  const el = (n2.el = n1.el)
  const oldProps = (n1 && n1.props) || EMPTY_OBJ
  const newProps = n2.props || EMPTY_OBJ
  // 更新 props
  patchProps(el, n2, oldProps, newProps, parentComponent, parentSuspense, isSVG)
  const areChildrenSVG = isSVG && n2.type !== 'foreignObject'
  // 更新子節(jié)點
  patchChildren(n1, n2, el, null, parentComponent, parentSuspense, areChildrenSVG)
}

• 主要做兩件事情
• 1、更新 props
  • patchProps 函數(shù)就是在更新 DOM 節(jié)點的 class、style、event 以及其它的一些 DOM 屬性
• 2、更新子節(jié)點，執(zhí)行patchChildren函數(shù)

const patchChildren = (n1, n2, container, anchor, parentComponent, parentSuspense, isSVG, optimized = false) => {
  const c1 = n1 && n1.children
  const prevShapeFlag = n1 ? n1.shapeFlag : 0
  const c2 = n2.children
  const { shapeFlag } = n2
  // 子節(jié)點有 3 種可能情況：文本、數(shù)組、空
  if (shapeFlag & 8 /* TEXT_CHILDREN */) {
    if (prevShapeFlag & 16 /* ARRAY_CHILDREN */) {
      // 數(shù)組 -> 文本，則刪除之前的子節(jié)點
      unmountChildren(c1, parentComponent, parentSuspense)
    }
    if (c2 !== c1) {
      // 文本對比不同，則替換為新文本
      hostSetElementText(container, c2)
    }
  }
  else {
    if (prevShapeFlag & 16 /* ARRAY_CHILDREN */) {
      // 之前的子節(jié)點是數(shù)組
      if (shapeFlag & 16 /* ARRAY_CHILDREN */) {
        // 新的子節(jié)點仍然是數(shù)組，則做完整地 diff
        patchKeyedChildren(c1, c2, container, anchor, parentComponent, parentSuspense, isSVG, optimized)
      }
      else {
        // 數(shù)組 -> 空，則僅僅刪除之前的子節(jié)點
        unmountChildren(c1, parentComponent, parentSuspense, true)
      }
    }
    else {
      // 之前的子節(jié)點是文本節(jié)點或者為空
      // 新的子節(jié)點是數(shù)組或者為空
      if (prevShapeFlag & 8 /* TEXT_CHILDREN */) {
        // 如果之前子節(jié)點是文本，則把它清空
        hostSetElementText(container, '')
      }
      if (shapeFlag & 16 /* ARRAY_CHILDREN */) {
        // 如果新的子節(jié)點是數(shù)組，則掛載新子節(jié)點
        mountChildren(c2, container, anchor, parentComponent, parentSuspense, isSVG, optimized)
      }
    }
  }
}

• 一個元素的子節(jié)點vnode 可能會有三種情況：純文本、vnode 數(shù)組和空

新舊對比，總共有九種情況

• 1、舊子節(jié)點是純文本
  • 如果新子節(jié)點也是純文本，那么做簡單地文本替換即可；
  • 如果新子節(jié)點是空，那么刪除舊子節(jié)點即可；
  • 如果新子節(jié)點是 vnode 數(shù)組，那么先把舊子節(jié)點的文本清空，再去舊子節(jié)點的父容器下添加多個新子節(jié)點
    
    image.png
• 2、舊子節(jié)點是空
  • 如果新子節(jié)點是純文本，那么在舊子節(jié)點的父容器下添加新文本節(jié)點即可；
  • 如果新子節(jié)點也是空，那么什么都不需要做；
  • 如果新子節(jié)點是 vnode數(shù)組，那么直接去舊子節(jié)點的父容器下添加多個新子節(jié)點即可
    
    image.png
• 3、舊子節(jié)點是 vnode 數(shù)組
  • 如果新子節(jié)點是純文本，那么先刪除舊子節(jié)點，再去舊子節(jié)點的父容器下添加新文本節(jié)點；
  • 如果新子節(jié)點是空，那么刪除舊子節(jié)點即可；
  • 如果新子節(jié)點也是vnode數(shù)組，那么就需要做完整的diff新舊子節(jié)點了，這是最復(fù)雜的情況，內(nèi)部運用了核心 diff 算法。
    
    image.png

核心 diff 算法

步驟1、同步頭部節(jié)點

const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
  let i = 0
  const l2 = c2.length
  // 舊子節(jié)點的尾部索引
  let e1 = c1.length - 1
  // 新子節(jié)點的尾部索引
  let e2 = l2 - 1
  // 1. 從頭部開始同步
  // i = 0, e1 = 3, e2 = 4
  // (a b) c d
  // (a b) e c d
  while (i <= e1 && i <= e2) {
    const n1 = c1[i]
    const n2 = c2[i]
    if (isSameVNodeType(n1, n2)) {
      // 相同的節(jié)點，遞歸執(zhí)行 patch 更新節(jié)點
      patch(n1, n2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized)
    }
    else {
      break
    }
    i++
  }
}

• 我們需要維護(hù)幾個變量：頭部的索引 i、舊子節(jié)點的尾部索引 e1和新子節(jié)點的尾部索引 e2。
• 從頭部開始，依次對比新節(jié)點和舊節(jié)點
• 如果它們相同的則執(zhí)行patch 更新節(jié)點
• 如果不同或者索引 i 大于索引 e1 或者e2，則同步過程結(jié)束
  
  image.png

步驟2、同步尾部節(jié)點

const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
  let i = 0
  const l2 = c2.length
  // 舊子節(jié)點的尾部索引
  let e1 = c1.length - 1
  // 新子節(jié)點的尾部索引
  let e2 = l2 - 1
  // 1. 從頭部開始同步
  // i = 0, e1 = 3, e2 = 4
  // (a b) c d
  // (a b) e c d
  // 2. 從尾部開始同步
  // i = 2, e1 = 3, e2 = 4
  // (a b) (c d)
  // (a b) e (c d)
  while (i <= e1 && i <= e2) {
    const n1 = c1[e1]
    const n2 = c2[e2]
    if (isSameVNodeType(n1, n2)) {
      patch(n1, n2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized)
    }
    else {
      break
    }
    e1--
    e2--
  }
}

• 同步尾部節(jié)點就是從尾部開始
• 依次對比新節(jié)點和舊節(jié)點
• 如果相同的則執(zhí)行 patch 更新節(jié)點；
• 如果不同或者索引 i 大于索引 e1 或者 e2，則同步過程結(jié)束
  
  image.png

步驟3、添加新的節(jié)點

const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
  let i = 0
  const l2 = c2.length
  // 舊子節(jié)點的尾部索引
  let e1 = c1.length - 1
  // 新子節(jié)點的尾部索引
  let e2 = l2 - 1
  // 1. 從頭部開始同步
  // i = 0, e1 = 3, e2 = 4
  // (a b) c d
  // (a b) e c d
  // ...
  // 2. 從尾部開始同步
  // i = 2, e1 = 3, e2 = 4
  // (a b) (c d)
  // (a b) e (c d)
  // 3. 掛載剩余的新節(jié)點
  // i = 2, e1 = 1, e2 = 2
  if (i > e1) {
    if (i <= e2) {
      const nextPos = e2 + 1
      const anchor = nextPos < l2 ? c2[nextPos].el : parentAnchor
      while (i <= e2) {
        // 掛載新節(jié)點
        patch(null, c2[i], container, anchor, parentComponent, parentSuspense, isSVG)
        i++
      }
    }
  }
}

• 如果索引 i 大于尾部索引 e1 且 i 小于 e2
• 那么從索引 i 開始到索引 e2 之間，我們直接掛載新子樹這部分的節(jié)點
  
  image.png

步驟4、刪除多余節(jié)點

const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
  let i = 0
  const l2 = c2.length
  // 舊子節(jié)點的尾部索引
  let e1 = c1.length - 1
  // 新子節(jié)點的尾部索引
  let e2 = l2 - 1
  // 1. 從頭部開始同步
  // i = 0, e1 = 4, e2 = 3
  // (a b) c d e
  // (a b) d e
  // ...
  // 2. 從尾部開始同步
  // i = 2, e1 = 4, e2 = 3
  // (a b) c (d e)
  // (a b) (d e)
  // 3. 普通序列掛載剩余的新節(jié)點
  // i = 2, e1 = 2, e2 = 1
  // 不滿足
  if (i > e1) {
  }
  // 4. 普通序列刪除多余的舊節(jié)點
  // i = 2, e1 = 2, e2 = 1
  else if (i > e2) {
    while (i <= e1) {
      // 刪除節(jié)點
      unmount(c1[i], parentComponent, parentSuspense, true)
      i++
    }
  }
}

• 如果索引 i 大于尾部索引 e2
• 那么從索引 i 開始到索引 e1 之間，我們直接刪除舊子樹這部分的節(jié)點。

處理未知子序列

image.png

移動子節(jié)點

var prev = [1, 2, 3, 4, 5, 6]
var next = [1, 3, 2, 6, 4, 5]

• 問題轉(zhuǎn)變?yōu)椋呵蠼庾铋L遞增子序列
• 在查找過程中需要對比新舊子序列，那么我們就要遍歷某個序列，如果在遍歷舊子序列的過程中需要判斷某個節(jié)點是否在新子序列中存在，這就需要雙重循環(huán)，而雙重循環(huán)的復(fù)雜度是 O(n2)，為了優(yōu)化這個復(fù)雜度，我們可以用一種空間換時間的思路，建立索引圖，把時間復(fù)雜度降低到 O(n)。

建立索引圖

• 通常我們在開發(fā)過程中， 會給 v-for 生成的列表中的每一項分配唯一key 作為項的唯一 ID
• 這個 key 在 diff 過程中起到很關(guān)鍵的作用。對于新舊子序列中的節(jié)點，我們認(rèn)為 key 相同的就是同一個節(jié)點，直接執(zhí)行 patch 更新即可。
• 根據(jù) key 建立新子序列的索引圖

const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
  let i = 0
  const l2 = c2.length
  // 舊子節(jié)點的尾部索引
  let e1 = c1.length - 1
  // 新子節(jié)點的尾部索引
  let e2 = l2 - 1
  // 1. 從頭部開始同步
  // i = 0, e1 = 7, e2 = 7
  // (a b) c d e f g h
  // (a b) e c d i g h
  // 2. 從尾部開始同步
  // i = 2, e1 = 7, e2 = 7
  // (a b) c d e f (g h)
  // (a b) e c d i (g h)
  // 3. 普通序列掛載剩余的新節(jié)點， 不滿足
  // 4. 普通序列刪除多余的舊節(jié)點，不滿足
  // i = 2, e1 = 4, e2 = 5
  // 舊子序列開始索引，從 i 開始記錄
  const s1 = i
  // 新子序列開始索引，從 i 開始記錄
  const s2 = i //
  // 5.1 根據(jù) key 建立新子序列的索引圖
  const keyToNewIndexMap = new Map()
  for (i = s2; i <= e2; i++) {
    const nextChild = c2[i]
    keyToNewIndexMap.set(nextChild.key, i)
  }
}

• 得到{e:2,c:3,d:4,i:5}
  
  image.png

更新和移除舊節(jié)點

const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
  let i = 0
  const l2 = c2.length
  // 舊子節(jié)點的尾部索引
  let e1 = c1.length - 1
  // 新子節(jié)點的尾部索引
  let e2 = l2 - 1
  // 1. 從頭部開始同步
  // i = 0, e1 = 7, e2 = 7
  // (a b) c d e f g h
  // (a b) e c d i g h
  // 2. 從尾部開始同步
  // i = 2, e1 = 7, e2 = 7
  // (a b) c d e f (g h)
  // (a b) e c d i (g h)
  // 3. 普通序列掛載剩余的新節(jié)點，不滿足
  // 4. 普通序列刪除多余的舊節(jié)點，不滿足
  // i = 2, e1 = 4, e2 = 5
  // 舊子序列開始索引，從 i 開始記錄
  const s1 = i
  // 新子序列開始索引，從 i 開始記錄
  const s2 = i
  // 5.1 根據(jù) key 建立新子序列的索引圖
  // 5.2 正序遍歷舊子序列，找到匹配的節(jié)點更新，刪除不在新子序列中的節(jié)點，判斷是否有移動節(jié)點
  // 新子序列已更新節(jié)點的數(shù)量
  let patched = 0
  // 新子序列待更新節(jié)點的數(shù)量，等于新子序列的長度
  const toBePatched = e2 - s2 + 1
  // 是否存在要移動的節(jié)點
  let moved = false
  // 用于跟蹤判斷是否有節(jié)點移動
  let maxNewIndexSoFar = 0
  // 這個數(shù)組存儲新子序列中的元素在舊子序列節(jié)點的索引，用于確定最長遞增子序列
  const newIndexToOldIndexMap = new Array(toBePatched)
  // 初始化數(shù)組，每個元素的值都是 0
  // 0 是一個特殊的值，如果遍歷完了仍有元素的值為 0，則說明這個新節(jié)點沒有對應(yīng)的舊節(jié)點
  for (i = 0; i < toBePatched; i++)
    newIndexToOldIndexMap[i] = 0
  // 正序遍歷舊子序列
  for (i = s1; i <= e1; i++) {
    // 拿到每一個舊子序列節(jié)點
    const prevChild = c1[i]
    if (patched >= toBePatched) {
      // 所有新的子序列節(jié)點都已經(jīng)更新，剩余的節(jié)點刪除
      unmount(prevChild, parentComponent, parentSuspense, true)
      continue
    }
    // 查找舊子序列中的節(jié)點在新子序列中的索引
    let newIndex = keyToNewIndexMap.get(prevChild.key)
    if (newIndex === undefined) {
      // 找不到說明舊子序列已經(jīng)不存在于新子序列中，則刪除該節(jié)點
      unmount(prevChild, parentComponent, parentSuspense, true)
    }
    else {
      // 更新新子序列中的元素在舊子序列中的索引，這里加 1 偏移，是為了避免 i 為 0 的特殊情況，影響對后續(xù)最長遞增子序列的求解
      newIndexToOldIndexMap[newIndex - s2] = i + 1
      // maxNewIndexSoFar 始終存儲的是上次求值的 newIndex，如果不是一直遞增，則說明有移動
      if (newIndex >= maxNewIndexSoFar) {
        maxNewIndexSoFar = newIndex
      }
      else {
        moved = true
      }
      // 更新新舊子序列中匹配的節(jié)點
      patch(prevChild, c2[newIndex], container, null, parentComponent, parentSuspense, isSVG, optimized)
      patched++
    }
  }
}

• patched為正在更新的索引，toBePatched為需要更新的長度， newIndexToOldIndexMap的數(shù)組，來存儲新子序列節(jié)點的索引和舊子序列節(jié)點的索引之間的映射關(guān)系
• patched > toBePatched，表明所有新的子序列節(jié)點都已經(jīng)更新，剩余的節(jié)點刪除
• keyToNewIndexMap.get(prevChild.key)獲取不到，表明不在新序列里，刪除
• 能找到，放入newIndexToOldIndexMap中，(此時為index+1，0有特殊作用)

移動和掛載新節(jié)點

const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
  let i = 0
  const l2 = c2.length
  // 舊子節(jié)點的尾部索引
  let e1 = c1.length - 1
  // 新子節(jié)點的尾部索引
  let e2 = l2 - 1
  // 1. 從頭部開始同步
  // i = 0, e1 = 6, e2 = 7
  // (a b) c d e f g
  // (a b) e c d h f g
  // 2. 從尾部開始同步
  // i = 2, e1 = 6, e2 = 7
  // (a b) c (d e)
  // (a b) (d e)
  // 3. 普通序列掛載剩余的新節(jié)點， 不滿足
  // 4. 普通序列刪除多余的節(jié)點，不滿足
  // i = 2, e1 = 4, e2 = 5
  // 舊子節(jié)點開始索引，從 i 開始記錄
  const s1 = i
  // 新子節(jié)點開始索引，從 i 開始記錄
  const s2 = i //
  // 5.1 根據(jù) key 建立新子序列的索引圖
  // 5.2 正序遍歷舊子序列，找到匹配的節(jié)點更新，刪除不在新子序列中的節(jié)點，判斷是否有移動節(jié)點
  // 5.3 移動和掛載新節(jié)點
  // 僅當(dāng)節(jié)點移動時生成最長遞增子序列
  const increasingNewIndexSequence = moved
    ? getSequence(newIndexToOldIndexMap)
    : EMPTY_ARR
  let j = increasingNewIndexSequence.length - 1
  // 倒序遍歷以便我們可以使用最后更新的節(jié)點作為錨點
  for (i = toBePatched - 1; i >= 0; i--) {
    const nextIndex = s2 + i
    const nextChild = c2[nextIndex]
    // 錨點指向上一個更新的節(jié)點，如果 nextIndex 超過新子節(jié)點的長度，則指向 parentAnchor
    const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAnchor
    if (newIndexToOldIndexMap[i] === 0) {
      // 掛載新的子節(jié)點
      patch(null, nextChild, container, anchor, parentComponent, parentSuspense, isSVG)
    }
    else if (moved) {
      // 沒有最長遞增子序列（reverse 的場景）或者當(dāng)前的節(jié)點索引不在最長遞增子序列中，需要移動
      if (j < 0 || i !== increasingNewIndexSequence[j]) {
        move(nextChild, container, anchor, 2)
      }
      else {
        // 倒序遞增子序列
        j--
      }
    }
  }
}

• moved 為 true 就通過 getSequence(newIndexToOldIndexMap)計算最長遞增子序列
• 采用倒序的方式遍歷新子序列，因為倒序遍歷可以方便我們使用最后更新的節(jié)點作為錨點。
• 錨點指向上一個更新的節(jié)點，然后判斷newIndexToOldIndexMap[i]是否為0，如果是則表示這是新節(jié)點，就需要掛載它
• 接著判斷是否存在節(jié)點移動的情況，如果存在的話則看節(jié)點的索引是不是在最長遞增子序列中，如果在則倒序最長遞增子序列，否則把它移動到錨點的前面

最長遞增子序列

• 動態(tài)規(guī)劃的思想，算法的時間復(fù)雜度是 O(n2)
• vuejs采用貪心 + 二分查找，總時間復(fù)雜度是O(nlogn)

arr：[2, 1, 5, 3, 6, 4, 8, 9, 7]
=> [1, 3, 4, 8, 9]

• 思路
  • 對數(shù)組遍歷
  • 當(dāng) i 元素大于 i - 1 的元素時，添加 i 元素并更新最長子序列
  • 否則往前查找直到找到一個比 i 小的元素，然后插在該元素后面并更新對應(yīng)的最長遞增子序列。

function getSequence (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) {
        // 存儲在 result 更新前的最后一個索引的值
        p[i] = j
        result.push(i)
        continue
      }
      u = 0
      v = result.length - 1
      // 二分搜索，查找比 arrI 小的節(jié)點，更新 result 的值
      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]
  // 回溯數(shù)組 p，找到最終的索引
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }
  return result
}

image.png