Vue3 diff 算法图解剖析

大家好，我是剑大瑞，本篇文章次要剖析 Vue3 diff 算法，通过本文你能够晓得：

• diff的次要过程，外围逻辑
• diff是如何进行节点复用、挪动、卸载
• 并有一个示例题，能够联合本文进行练习剖析

如果你还不是特地理解 Vnode、渲染器的patch 流程，倡议先浏览上面两篇文章：

• Vnode
• 渲染器剖析

1.0 diff 无 key 子节点

在解决被标记为 UNKEYED_FRAGMENT 时。

• 首先会通过新旧子序列获取最小独特长度commonLength。
• 对公共局部循环遍历patch。
• patch 完结，再解决残余的新旧节点。
• 如果oldLength > newLength，阐明须要对旧节点进行unmount

• 否则，阐明有新增节点，须要进行mount;

这里贴下省略后的代码。

const patchUnkeyedChildren = (c1, c2,...res) => {
    c1 = c1 || EMPTY_ARR
    c2 = c2 || EMPTY_ARR
    // 获取新旧子节点的长度
    const oldLength = c1.length
    const newLength = c2.length
    // 1. 获得公共长度。最小长度
    const commonLength = Math.min(oldLength, newLength)
    let i
    // 2. patch 公共局部
    for (i = 0; i < commonLength; i++) {patch(...)
    }
    // 3. 卸载旧节点
    if (oldLength > newLength) {
      // remove old
      unmountChildren(...)
    } else {
      // mount new
      // 4. 否则挂载新的子节点
      mountChildren(...)
    }
  }

从下面的代码能够看出，在解决无 key 子节点的时候，逻辑还是非常简单粗犷的。精确的说解决无 key 子节点的效率并不高。

因为不论是间接对公共局部 patch，还是间接对新增节点进行mountChildren（其实是遍历子节点，进行patch 操作），其实都是在递归进行patch，这就会影响到性能。

2.0 diff 有 key 子节点序列

在 diff 有key子序列的时候，会进行细分解决。次要会通过以下一种状况的判断：

• 起始地位节点类型雷同。
• 完结地位节点类型雷同。
• 雷同局部解决完，有新增节点。
• 雷同局部解决完，有旧节点须要卸载。
• 首尾雷同，但两头局部存在可复用乱序节点。

在开始阶段，会学生面三个斧正，别离是:

• i = 0，指向新旧序列的开始地位
• e1 = oldLength - 1，指向旧序列的完结地位
• e2 = newLength - 1，指向新序列的完结地位

let i = 0
const l2 = c2.length
let e1 = c1.length - 1 // prev ending index
let e2 = l2 - 1 // next ending index

上面开始分状况进行 diff 解决。

2.1 起始地位节点类型雷同

• 对于起始地位类型雷同的节点，从左向右进行 diff 遍历。
• 如果新旧节点类型雷同，则进行 patch 解决
• 节点类型不同，则break，跳出遍历diff

//  i <= 2 && i <= 3
while (i <= e1 && i <= e2) {const n1 = c1[i]
  const n2 = c2[i]
  if (isSameVNodeType(n1, n2)) {
    // 如果是雷同的节点类型，则进行递归 patch
    patch(...)
  } else {
    // 否则退出
    break
  }
  i++
}

下面上略了局部代码，但不影响次要逻辑。

从代码能够晓得，遍历时，利用后面在函数全局上下文中申明的三个指针，进行遍历判断。

保障能充沛遍历到开始地位雷同的地位，i <= e1 && i <= e2。

一旦遇到类型不同的节点，就会跳出 diff 遍历。

2.2 完结地位节点类型雷同

开始地位雷同diff 完结，会紧接着从序列尾部开始遍历 diff。

此时须要对尾指针 e1、e2 进行递加。

//  i <= 2 && i <= 3
// 完结后：e1 = 0 e2 =  1
while (i <= e1 && i <= e2) {const n1 = c1[e1]
  const n2 = c2[e2]
  if (isSameVNodeType(n1, n2)) {
    // 雷同的节点类型
    patch(...)
  } else {
    // 否则退出
    break
  }
  e1--
  e2--
}

从代码能够看出，diff逻辑与第一种根本一样，雷同类型进行 patch 解决。

不同类型break，跳出循环遍历。

并且对尾指针进行递加操作。

2.3 雷同局部遍历完结，新序列中有新增节点，进行挂载

通过下面两种状况的解决，曾经 patch 完首尾雷同局部的节点，接下来是对新序列中的新增节点进行 patch 解决。

在通过下面两种请款解决之后，如果有新增节点，可能会呈现 i > e1 && i <= e2的状况。

这种状况下意味着新的子节点序列中有新增节点。

这时会对新增节点进行patch。

// 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
    // nextPos < l2，阐明有曾经 patch 过尾部节点，// 否则会获取父节点作为锚点
    const anchor = nextPos < l2 ? c2[nextPos].el : parentAnchor
    while (i <= e2) {patch(null, c2[i], anchor, ...others)
      i++
    }
  }
}

从下面的代码能够晓得，patch的时候没有传第一个参数，最终会走 mount 的逻辑。

能够看这篇次要剖析 patch 的过程

在 patch 的过程中，会递增 i 指针。

并通过 nextPos 来获取锚点。

如果 nextPos < l2，则以曾经patch 的节点作为锚点，否则以父节点作为锚点。

2.4 雷同局部遍历完结，新序列中少节点，进行卸载

如果解决完收尾雷同的节点，呈现 i > e2 && i <= e1 的状况，则意味着有旧节点须要进行卸载操作。

// 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++
  }
}

通过代码能够晓得，这种状况下，会递增 i 指针，对旧节点进行卸载。

2.5 乱序状况

这种状况下较为简单，但 diff 的外围逻辑在于通过新旧节点的地位变动构建一个最大递增子序列，最大子序列能保障通过最小的挪动或者 patch 实现节点的复用。

上面一起来看下如何实现的。

2.5.1 为新子节点构建 key:index 映射

// 5. 乱序的状况
// [i ... e1 + 1]: a b  f g
// [i ... e2 + 1]: a b [e d c h] f g
// i = 2, e1 = 4, e2 = 5

const s1 = i // s1 = 2
const s2 = i // s2 = 2

// 5.1 build key:index map for newChildren
// 首先为新的子节点构建在新的子序列中 key：index 的映射
// 通过 map 创立的新的子节点
const keyToNewIndexMap = new Map()
// 遍历新的节点，为新节点设置 key
// i = 2; i <= 5
for (i = s2; i <= e2; i++) {
  // 获取的是新序列中的子节点
  const nextChild = c2[i];
  if (nextChild.key != null) {
    // nextChild.key 已存在
    // a b [e d c h] f g
    // e:2 d:3 c:4 h:5
    keyToNewIndexMap.set(nextChild.key, i)
  }
}

联合下面的图和代码能够晓得：

• 在通过首尾雷同的 patch 解决之后，i = 2，e1 = 4，e2 = 5
• 通过遍历之后 keyToNewIndexMap 中，新节点的 key:index 的关系为 E : 2、D : 3、C : 4、H : 5
• keyToNewIndexMap的作用次要是前面通过遍历旧子序列，确定可复用节点在新的子序列中的地位

2.5.2 从左向右遍历旧子序列，patch匹配的雷同类型的节点，移除不存在的节点

通过后面的解决，曾经创立了keyToNewIndexMap。

在开始从左向右遍历之前，须要晓得几个变量的含意：

// 5.2 loop through old children left to be patched and try to patch
// matching nodes & remove nodes that are no longer present
// 从旧的子节点的左侧开始循环遍历进行 patch。// 并且 patch 匹配的节点 并移除不存在的节点

// 曾经 patch 的节点个数
let patched = 0
// 须要 patch 的节点数量
// 以上图为例：e2 = 5; s2 = 2; 晓得须要 patch 的节点个数
// toBePatched = 4
const toBePatched = e2 - s2 + 1
// 用于判断节点是否须要挪动
// 当新旧队列中呈现可复用节点穿插时，moved = true
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
// 留神 旧节点的 index 要向右偏移一个下标

// and oldIndex = 0 is a special value indicating the new node has
// no corresponding old node.
// 并且旧节点 Index = 0 是一个非凡的值，用于示意新的节点中没有对应的旧节点

// used for determining longest stable subsequence
// newIndexToOldIndexMap 用于确定最长递增子序列
// 新下标与旧下标的 map
const newIndexToOldIndexMap = new Array(toBePatched)
// 将所有的值初始化为 0
// [0, 0, 0, 0]
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0

• 变量 patched 用于记录曾经 patch 的节点
• 变量 toBePatched 用于记录须要进行 patch 的节点个数
• 变量 moved 用于记录是否有可复用节点产生穿插
• maxNewIndexSoFar用于记录当旧的子序列中存在没有设置 key 的子节点，然而该子节点呈现于新的子序列中，且可复用，最大下标。
• 变量 newIndexToOldIndexMap 用于映射 新的子序列中的节点下标 对应于 旧的子序列中的节点的下标
• 并且会将 newIndexToOldIndexMap 初始化为一个全 0 数组，[0, 0, 0, 0]

晓得了这些变量的含意之后 咱们就能够开始从左向右遍历子序列了。

遍历的时候，须要首先遍历旧子序列，终点是s1，起点是e1。

遍历的过程中会对 patched 进行累加。

卸载旧节点

如果patched >= toBePatched，阐明新子序列中的子节点少于旧子序列中的节点数量。

须要对旧子节点进行卸载。

// 遍历未解决旧序列中子节点
for (i = s1; i <= e1; i++) {
    // 获取旧节点
    // 会一一获取 c d e
    const prevChild = c1[i]
    // 如果曾经 patch 的数量 >= 须要进行 patch 的节点个数
    
    // patched 刚开始为 0
    // patched >= 4
    if (patched >= toBePatched) {
      // all new children have been patched so this can only be a removal
      // 这阐明所有的新节点曾经被 patch 因而能够移除旧的
      unmount(prevChild, parentComponent, parentSuspense, true)
      continue
    }
}

如果 prevChild.key 是存在的，会通过后面咱们构建的 keyToNewIndexMap，获取prevChild 在新子序列中的下标newIndex。

获取newIndex

// 新节点下标
let newIndex
if (prevChild.key != null) {
  // 旧的节点必定有 key, 
  // 依据旧节点 key  获取雷同类型的新的子节点  在 新的队列中对应节点地位
  // 这个时候 因为 c d e 是原来的节点 并且有 key
  // h 是新增节点 旧节点中没有 获取不到 对应的 index 会走 else
  // 所以 newIndex 在开始时会有如下状况
  /**
   * node  newIndex
   *  c       4
   *  d       3
   *  e       2
   * */ 
  // 这里是能够获取到 newIndex 的
  newIndex = keyToNewIndexMap.get(prevChild.key)
}

以图为例，能够晓得，在遍历过程中，节点 c、d、e 为可复用节点，别离对应新子序列中的 2、3、4 的地位。

故 newIndex 能够取到的值为4、3、2。

如果旧节点没有 key 怎么办？

// key-less node, try to locate a key-less node of the same type
// 如果旧的节点没有 key
// 则会查找没有 key 的 且为雷同类型的新节点在 新节点队列中 的地位
// j = 2: j <= 5
for (j = s2; j <= e2; j++) {
  if (newIndexToOldIndexMap[j - s2] === 0 &&
    // 判断是否是新旧节点是否雷同
    isSameVNodeType(prevChild, c2[j])
  ) {
    // 获取到雷同类型节点的下标
    newIndex = j
    break
  }
}

如果节点没有 key，则同样会取新子序列中，遍历查找没有key 且两个新旧类型雷同子节点，并以此节点的下标，作为newIndex。

newIndexToOldIndexMap[j – s2] === 0 阐明节点没有该节点没有 key。

如果还没有获取到 newIndex，阐明在新子序列中没有存在的与 prevChild 雷同的子节点，须要对prevChild 进行卸载。

if (newIndex === undefined) {
  // 没有对应的新节点 卸载旧的
  unmount(prevChild, parentComponent, parentSuspense, true)
}

否则，开始依据newIndex，构建keyToNewIndexMap，明确新旧节点对应的下标地位。

时刻牢记 newIndex 是依据旧节点获取的其在新的子序列中的下标。

// 这里解决获取到 newIndex 的状况
// 开始整顿新节点下标 Index 对于 雷同类型旧节点在 旧队列中的映射
// 新节点下标从 s2=2 开始，对应的旧节点下标须要偏移一个下标
// 0 示意以后节点没有对应的旧节点
// 偏移 1 个地位 i 从 s1 = 2 开始，s2 = 2
// 4 - 2 获取下标 2，新的 c 节点对应旧 c 节点的地位下标 3
// 3 - 2 获取下标 1，新的 d 节点对应旧 d 节点的地位下标 4
// 2 - 2 获取下标 0，新的 e 节点对应旧 e 节点的地位下标 5
// [0, 0, 0, 0] => [5, 4, 3, 0]
// [2,3,4,5] = [5, 4, 3, 0]
newIndexToOldIndexMap[newIndex - s2] = i + 1
// newIndex 会取 4 3 2
/** 
 *   newIndex  maxNewIndexSoFar   moved
 *       4            0          false
 *       3            4           true
 *       2        
 * 
 * */ 
if (newIndex >= maxNewIndexSoFar) {maxNewIndexSoFar = newIndex} else {moved = true}

在构建 newIndexToOldIndexMap 的同时，会通过判断 newIndex、maxNewIndexSoFa 的关系，确定节点是否产生挪动。

newIndexToOldIndexMap最初遍历完结应该为 [5, 4, 3, 0]，0 阐明有旧序列中没有与心序列中对应的节点，并且该节点可能是新增节点。

如果新旧节点在序列中绝对地位放弃始终不变，则 maxNewIndexSoFar 会随着 newIndex 的递增而递增。

意味着节点没有产生穿插。也就不须要挪动可复用节点。

否则可复用节点产生了挪动，须要对可复用节点进行move。

遍历的最初，会对新旧节点进行 patch，并对patched 进行累加，记录曾经解决过几个节点。

// 进行递归 patch
/**
 * old   new
 *  c     c
 *  d     d
 *  e     e 
*/
patch(
  prevChild,
  c2[newIndex],
  container,
  null,
  parentComponent,
  parentSuspense,
  isSVG,
  slotScopeIds,
  optimized
)
// 曾经 patch 的
patched++

通过下面的解决，曾经实现对旧节点进行了卸载，对绝对地位放弃没有变动的子节点进行了 patch 复用。

接下来就是须要挪动可复用节点，挂载新子序列中新增节点。

2.5.3 挪动可复用节点，挂载新增节点

这里波及到一块比拟外围的代码，也是 Vue3 diff 效率晋升的关键所在。

后面通过newIndexToOldIndexMap，记录了新旧子节点变动前后的下标映射。

这里会通过 getSequence 办法获取一个最大递增子序列。用于记录绝对地位没有发生变化的子节点的下标。

依据此递增子序列，能够实现在挪动可复用节点的时候，只挪动绝对地位前后发生变化的子节点。

做到最小改变。

那什么是最大递增子序列？

• 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不扭转其余元素的程序。
• 而递增子序列，是数组派生的子序列，各元素之间放弃一一递增的关系。
• 例如：
• 数组[3, 6, 2, 7] 是数组 [0, 3, 1, 6, 2, 2, 7] 的最长严格递增子序列。
• 数组 [2, 3, 7, 101] 是数组 [10 , 9, 2, 5, 3, 7, 101, 18] 的最大递增子序列。
• 数组 [0, 1, 2, 3] 是数组 [0, 1, 0, 3, 2, 3] 的最大递增子序列。

已上图为例，在未解决的乱序节点中，存在 新增节点 N、I、须要卸载的 节点 G ，及可复用 节点 C、D、E、F。

节点 CDE在新旧子序列中绝对地位没有变换，如果想要通过最小变动实现节点复用，咱们能够将找出 F 节点 变动前后的下标地位，在新的子序列 C 节点 之前插入 F 节点 即可。

最大递增子序列的作用就是通过新旧节点变动前后的映射，创立一个递增数组，这样就能够晓得哪些节点在变动前后绝对地位没有发生变化，哪些节点须要进行挪动。

Vue3中的递增子序列的不同在于，它保留的是可复用节点在 newIndexToOldIndexMap的下标。而并不是 newIndexToOldIndexMap 中的元素。

接下来咱们看下代码局部：

// 5.3 move and mount
// generate longest stable subsequence only when nodes have moved
// 挪动节点 挂载节点
// 仅当节点被挪动后 生成最长递增子序列
// 通过下面操作后，newIndexToOldIndexMap = [5, 4, 3, 0]
// 失去 increasingNewIndexSequence = [2]
const increasingNewIndexSequence = moved
  ? getSequence(newIndexToOldIndexMap)
  : EMPTY_ARR
// j = 0
j = increasingNewIndexSequence.length - 1
// looping backwards so that we can use last patched node as anchor
// 从后向前遍历 以便于能够用最新的被 patch 的节点作为锚点
// i = 3
for (i = toBePatched - 1; i >= 0; i--) {
  // 5 4 3 2
  const nextIndex = s2 + i
  // 节点 h  c  d  e 
  const nextChild = c2[nextIndex]
  // 获取锚点
  const anchor =
    nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAnchor
  // [5, 4, 3, 0] 节点 h 会被 patch，其实是 mount
  //  c  d  e 会被挪动
  if (newIndexToOldIndexMap[i] === 0) {
    // mount new
    // 挂载新的
    patch(
      null,
      nextChild,
      container,
      anchor,
      ...
    )
  } 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, MoveType.REORDER)
    } else {j--}
  }
}

从下面的代码能够晓得：

• 通过 newIndexToOldIndexMap 获取的最大递增子序列是[2]
• j = 0
• 遍历的时候从右向左遍历，这样能够获取到锚点，如果有曾经通过 patch 的兄弟节点，则以兄弟节点作为锚点，否则以父节点作为锚点
• newIndexToOldIndexMap[i] === 0，阐明是新增节点。须要对节点进行 mount，这时只需给patch 的第一个参数传 null 即可。能够晓得首先会对 h 节点 进行patch。
• 否则会判断 moved 是否为 true。通过后面的剖析，咱们晓得 节点 C & 节点 E 在前后变动中产生了地位挪动。
• 故这里会挪动节点，咱们晓得 j 此时为 0，i 此时为2，i !== increasingNewIndexSequence[j] 为 true，并不会挪动 C 节点，而是执行 j--。
• 前面因为 j < 0，会对 D、E 节点 进行挪动。

至此咱们就实现了 Vue3 diff 算法的学习剖析。

这里为大家提供了一个示例，能够联合本文的剖析过程进行练习：

能够只看第一张图进行剖析，剖析完结后能够与第二三张图片进行比照。

图一：

图二 & 三：

总结

通过下面的学习剖析，能够晓得，Vue3 的 diff 算法，会首先进行收尾雷同节点的 patch 解决，完结后，会挂载新增节点，卸载旧节点。

如果子序列的状况较为简单，比方呈现乱序的状况，则会首先找出可复用的节点，并通过可复用节点的地位映射构建一个最大递增子序列，通过最大递增子序列来对节点进行 mount & move。以进步diff 效率，实现节点复用的最大可能性。