一线大厂高级前端编写,前端初中阶面试题,帮助初学者应聘,需要联系微信:javadudu

Vue3源码解析之 diff(二)

本文为原创文章,未获授权禁止转载,侵权必究!

本篇是 Vue3 源码解析系列第 18 篇,关注专栏

前言

上一篇我们分析了 diff 算法的前四步逻辑,第五步 乱序比对 逻辑 Vue 又分了三步来进行,那什么是 乱序比对 呢?我们知道节点的比较存在新增删除位置交换内容更替等场景,通过前四步逻辑处理完后,剩余的节点依旧存在上述多种情况,这时我们就要采用 乱序比对 逻辑,接下来我们针对该逻辑逐一分析。

案例

首先引入 h 、 render函数,先渲染 vnode1 对象,它包含五个子节点 a b c d ekey1 2 3 4 5,两秒后更新渲染 vnode2 对象,为了区分我们修改其内容,内容分别为 new-a new-c new-b new-f new-fkey1 3 2 6 5

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
    <script src="../../../dist/vue.global.js"></script>
  </head>

  <body>
    <div id="app"></div>
    <script>
     const { h, render } = Vue

      const vnode1 = h('ul', [
        h('li', { key: 1 }, 'a'),
        h('li', { key: 2 }, 'b'),
        h('li', { key: 3 }, 'c'),
        h('li', { key: 4 }, 'd'),
        h('li', { key: 5 }, 'e')
      ])

      render(vnode1, document.querySelector('#app'))

      setTimeout(() => {
        const vnode2 = h('ul', [
          h('li', { key: 1 }, 'new-a'),
          h('li', { key: 3 }, 'new-c'),
          h('li', { key: 2 }, 'new-b'),
          h('li', { key: 6 }, 'new-f'),
          h('li', { key: 5 }, 'new-e')
        ])

        render(vnode2, document.querySelector('#app'))
      }, 2000)
    </script>
  </body>
</html>

Vue3源码解析之 diff(二)

案例分析

通过上述案例,我们得知,a e 节点只是更新了内容,而 b c 节点需交替位置,d 节点需删除,f 节点需新增。接下来我们执行 diff 算法逻辑,先执行第一步 自前向后,第一个节点比较 typekey 相同,执行 patch 挂载更新,此时页面呈现:

Vue3源码解析之 diff(二)

由于第二节点比较 key 不同,直接 break 跳出循环,执行第二步逻辑 自后向前,最后个节点比较 typekey 相同,执行 patch 挂载更新,此时页面呈现:

Vue3源码解析之 diff(二)

第三、第四步逻辑条件均未满足,执行第五步逻辑即 乱序比对

根据案例,还剩余 b c d 节点未处理,当前 e1 = 3(旧节点结束下标)e2 = 3(新节点结束下标)i = 1(开始节点下标)l2 = 5(新节点数量),可以看出 e1 对应旧节点的 de2 对应新节点的 new-fi 分别对应旧节点的 b 和新节点的 new-c

Vue3源码解析之 diff(二)

最长递增子序列

乱序比对 逻辑中,Vue 使用了 最长递增子序列 这样的一个概念。那什么是最长递增子序列呢?维基百科 这样定义: 在一个给定的数值序列中,找到一个子序列,使得这个子序列元素的数值依次递增,并且这个子序列的长度尽可能地大。

举个例子:

旧节点:1, 2, 3, 4, 5, 6

新节点:1, 3, 2, 4, 6, 5

我们根据新节点生成 递增子序列(非最长且并不是唯一的),其结果为:

  1. 1, 3, 6
  2. 1, 2, 4, 5

先依据第一个 1, 3, 6,这三个不动,那么就要移动 2, 4, 5 三个做对应的移动,而依据 1, 2, 4, 5,则只需移动 3, 6 两个。至此,我们可以理解为 递增子序列 最长的一个移动次数最少。

Vue 中通过 getSequence 方法来获取 最长递增子序列,该方法定义在 packages/runtime-core/src/renderer.ts 文件中:

function getSequence(arr: number[]): number[] {
  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) {
        p[i] = j
        result.push(i)
        continue
      }
      u = 0
      v = result.length - 1
      while (u < v) {
        c = (u + v) >> 1
        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]
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }
  return result
}

这里稍微有点区别,该方法是获取 最长递增子序列的下标,根据上面例子,最长递增子序列为 1, 2, 4, 5 则下标就是 0, 2, 3, 5,我们可以将该方法抽离出来写个例子:

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      function getSequence(arr) {
        // p 是一个最终的回溯数组,它会在最终的 result 回溯中被使用
        // 它会在每次 result 发生变化时,记录 result 更新前最后一个索引的值
        const p = arr.slice() // 浅拷贝数组
        // 定义返回值(最长递增子序列下标),因为下标从 0 开始,所以它的初始值为 0
        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] // 下标数组最后一个元素 即:当前 result 中保存的最大值的下标
            if (arr[j] < arrI) {
              // 下标数组最后一个对应数组的值 和 当前数组值比较
              p[i] = j
              result.push(i)
              continue
            }
            
           // 不满足 arr[j] < arrI 的条件,就证明目前 result 中的最后位置保存着最大数值的下标。
           // 但是这个下标并不一定是一个递增的序列,比如: [1, 3] 和 [1, 2]
           // 所以我们还需要确定当前的序列是递增的。
           // 计算方式就是通过:二分查找来进行的
            
            u = 0 // 初始下标
            v = result.length - 1 // 最终下标
            while (u < v) {
              // 二分查找
              c = (u + v) >> 1 // 找中间位
              if (arr[result[c]] < arrI) {
                // u(初始下标)= 中间位 + 1 从中间向右移动一位,作为初始下标。
                //(下次直接从中间开始,往后计算即可)
                u = c + 1 
              } else {
                // v(最终下标) = 中间位。即:下次直接从 0 开始,计算到中间位置 即可。
                v = c 
              }
            }
            // arrI < arr[result[u]] 证明当前 result 中存在的下标 不是 递增序列,则需要进行替换
            if (arrI < arr[result[u]]) {
              if (u > 0) {
                p[i] = result[u - 1]
              }
              result[u] = i // 替换为递增序列
            }
          }
        }
        // 回溯逻辑
        // 重新定义 u。此时:u = result 的长度
        u = result.length
        // 重新定义 v。此时 v = result 的最后一个元素
        v = result[u - 1]
        // 自后向前处理 result,利用 p 中所保存的索引值,进行最后的一次回溯
        while (u-- > 0) {
          result[u] = v
          v = p[v]
        }
        return result
      }

      console.log(getSequence([1, 3, 2, 4, 6, 5]))
    </script>
  </body>
</html>

p 浅拷贝一份传入的数组,由于数组下标是从 0 开始的,所以 result 初始值为 [0]。之后遍历数组,判断当前值不为 0,接着设置 j下标数组 result 最后一个元素,即当前 result 中保存的最大值的下标

然后根据下标值 j 获取到传入数组对应的值 arr[j] 和 当前值 arrI 比较,我们直接从第二次遍历查看,j = 0i = 1,此时 p 没修改前:

Vue3源码解析之 diff(二)

修改后 p[i] = j

Vue3源码解析之 diff(二)

可见 p 作用它会在 result 发生变化时,记录 result 更新前最后一个索引值,之后再将当前下标 i 插入 result 中,此时结果为:

Vue3源码解析之 diff(二)

第三次遍历,arr[j] < arr[i]3 < 2 不满足条件,就证明目前 result 中的最后位置保存着最大数值的下标,但这个下标并不一定是一个递增的序列,比如: [1, 3][1, 2],所以我们还需要确定当前的序列是递增的,计算方式就是通过 二分查找 来进行。

后续执行 while 遍历,我们可以理解为这段是 二分查找u 为初始下标,v 为最终下标,当前 v1(0 + 1) >> 1 右移算出中间位 c,当前右移 1 位,等于 1 除以 2 得到 0

之后从 result 中根据 c(中间位) 取出中间位的下标,然后利用中间位的下标,从传入的数组 arr 中取出对应的值 arr[result[c]],和当前值 arrI 比较。如果小于,则 u(初始下标)= 中间位 + 1,即:从中间向右移动一位,作为初始下标(下次直接从中间开始,往后计算即可)。否则 v(最终下标)= 中间位,即:下次直接从 0 开始,计算到中间位置 即可。

根据计算得到目标下标位 u,此时为 1

Vue3源码解析之 diff(二)

利用 uresult 中获取 下标,然后拿到 arr 中对应的值 arr[result[u]] 和当前值 arrI 比较。如果 arrI < arr[result[u]] ,则证明当前 result 中存在的下标 不是 递增序列,则需要进行替换。当前 2 < 3 满足条件,重新计算 presult 值:

Vue3源码解析之 diff(二)

遍历完成,此时 resultp 对应的值:

Vue3源码解析之 diff(二)

最后一段逻辑做了回溯处理,与原来一致,我们再看下打印的结果:

Vue3源码解析之 diff(二)

乱序比对

讲完了 最长递增子序列,我们回过来再看下第五段逻辑:

else {
// 旧子节点的开始索引
const s1 = i // prev starting index
// 新子节点的开始索引
const s2 = i // next starting index
// 5.1 build key:index map for newChildren
// 5.1 创建一个 <key(新节点的 key):index(新节点的位置)> 的 Map 对象 keyToNewIndexMap。
// 通过该对象可知:新的 child(根据 key 判断指定 child) 更新后的位置(根据对应的 index 判断)在哪里
const keyToNewIndexMap: Map<string | number | symbol, number> = new Map()
// 通过循环为 keyToNewIndexMap 填充值
for (i = s2; i <= e2; i++) {
// 从 c2 中根据开始索引获取每一个 child
const nextChild = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]))
// child 必须存在 key(这也是为什么 v-for 必须要有 key 的原因)  
if (nextChild.key != null) {
if (__DEV__ && keyToNewIndexMap.has(nextChild.key)) {
warn(
`Duplicate keys found during update:`,
JSON.stringify(nextChild.key),
`Make sure keys are unique.`
)
}
// 把 key 和 对应的索引,放到 keyToNewIndexMap 对象中
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
// 5.2 循环 oldChildren ,并尝试进行 patch(打补丁)或 unmount(删除)旧节点
let j
// 记录已经修复的新节点数量
let patched = 0
// 新节点待修补的数量 = e2 - s2 + 1
const toBePatched = e2 - s2 + 1
// 标记位:节点是否需要移动
let moved = false
// used to track whether any node has moved
// 配合 moved 进行使用,它始终保存当前最大的 index 值
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
// 创建一个 Array 的对象,用来确定最长递增子序列。
// 它的下标表示:新节点的下标(newIndex),不计算已处理的节点,元素表示:对应旧节点的下标(oldIndex),永远 +1
// 但是,需要特别注意的是:oldIndex 的值应该永远 +1 
//(因为 0 代表了特殊含义,他表示 新节点没有找到对应的旧节点,此时需要新增新节点)。
// 即:旧节点下标为 0, 但是记录时会被记录为 1
const newIndexToOldIndexMap = new Array(toBePatched)
// 遍历 toBePatched ,为 newIndexToOldIndexMap 进行初始化,初始化时,所有的元素为 0
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
// 遍历 e1,获取旧节点,
// 如果当前 已经处理的节点数量 > 待处理的节点数量,
// 那么就证明:所有的节点都已经更新完成,剩余的旧节点全部删除即可
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
// 旧节点的 key 存在时
if (prevChild.key != null) {
// 根据旧节点的 key,从 keyToNewIndexMap 中可以获取到新节点对应的位置
newIndex = keyToNewIndexMap.get(prevChild.key)
} else {
// key-less node, try to locate a key-less node of the same type
// 旧节点的 key 不存在(无 key 节点)
// 那么我们就遍历所有的新节点,找到 没有找到对应旧节点的新节点,并且该新节点可以和旧节点匹配,
// 如果能找到,那么 newIndex = 该新节点索引
for (j = s2; j <= e2; j++) {
// 找到 没有找到对应旧节点的新节点,并且该新节点可以和旧节点匹配
if (
newIndexToOldIndexMap[j - s2] === 0 &&
isSameVNodeType(prevChild, c2[j] as VNode)
) {
// 如果能找到,那么 newIndex = 该新节点索引
newIndex = j
break
}
}
}
// 最终没有找到新节点的索引,则证明:当前旧节点没有对应的新节点
if (newIndex === undefined) {
// 此时,直接删除即可
unmount(prevChild, parentComponent, parentSuspense, true)
} 
// 没有进入 if,则表示:当前旧节点找到了对应的新节点,
// 那么接下来就是要判断对于该新节点而言,是要 patch(打补丁)还是 move(移动)
else { 
// 为 newIndexToOldIndexMap 填充值:
// 下标表示:新节点的下标(newIndex),不计算已处理的节点。元素表示:对应旧节点的下标(oldIndex),永远 +1
// 因为 newIndex 包含已处理的节点,所以需要减去 s2,表示:不计算已处理的节点
newIndexToOldIndexMap[newIndex - s2] = i + 1
// maxNewIndexSoFar 会存储当前最大的 newIndex,它应该是一个递增的,
// 如果没有递增,则证明有节点需要移动
if (newIndex >= maxNewIndexSoFar) {
// 持续递增
maxNewIndexSoFar = newIndex
} else {
// 没有递增,则需要移动,moved = true
moved = true
}
// 打补丁
patch(
prevChild,
c2[newIndex] as VNode,
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 >= 0 表示:初始值为 最长递增子序列的最后下标
// j < 0 表示:不存在最长递增子序列。  
j = increasingNewIndexSequence.length - 1
// looping backwards so that we can use last patched node as anchor
// 倒序循环,以便我们可以使用最后修补的节点作为锚点
for (i = toBePatched - 1; i >= 0; i--) {
// nextIndex(需要更新的新节点下标) = s2 + i
const nextIndex = s2 + i
// 根据 nextIndex 拿到要处理的 新节点
const nextChild = c2[nextIndex] as VNode
// 获取锚点(是否超过了最长长度)
const anchor =
nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor
// 如果 newIndexToOldIndexMap 中保存的 value = 0,
// 则表示:新节点没有用对应的旧节点,此时需要挂载新节点  
if (newIndexToOldIndexMap[i] === 0) {
// mount new
// 挂载新节点
patch(
null,
nextChild,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
} 
// moved 为 true,表示需要移动
else if (moved) {
// move if:
// There is no stable subsequence (e.g. a reverse)
// OR current node is not among the stable sequence
// j < 0 表示:不存在 最长递增子序列
// i !== increasingNewIndexSequence[j] 表示:当前节点不在最后位置
// 那么此时就需要 move (移动)
if (j < 0 || i !== increasingNewIndexSequence[j]) {
move(nextChild, container, anchor, MoveType.REORDER)
} else {
// j 随着循环递减
j--
}
}
}
}

该逻辑又分了三部分来进行处理,结合案例,a e 节点已处理完毕,还剩余 b c d 节点未处理。当前 e1 = 3(旧节点结束下标)e2 = 3(新节点结束下标)i = 1(开始节点下标)l2 = 5(新节点数量)。我们先看下第一段逻辑:

const s1 = i // prev starting index
const s2 = i // next starting index
// 5.1 build key:index map for newChildren
const keyToNewIndexMap: Map<string | number | symbol, number> = new Map()
for (i = s2; i <= e2; i++) {
const nextChild = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]))
if (nextChild.key != null) {
if (__DEV__ && keyToNewIndexMap.has(nextChild.key)) {
warn(
`Duplicate keys found during update:`,
JSON.stringify(nextChild.key),
`Make sure keys are unique.`
)
}
keyToNewIndexMap.set(nextChild.key, i)
}
}

该逻辑主要是构建 keyToNewIndexMap map对象,将新节点的 key 作为 ,新节点的 下标 作为 s1 为旧节点的开始下标,s2 为新节点的开始下标,e2 为新节点的结束下标。

之后遍历新节点,先获取当前新节点 new-c,判断当前新节点的 key 是否存在,这也就是为什么 v-for 必须设置 key 的原因,对于当前判断 key 必须存在且不能重复,接着将 新节点的 key 作为 ,新节点的 下标 作为 来设置 keyToNewIndexMap 对象,遍历执行完,结果为:

Vue3源码解析之 diff(二)

new-c new-b new-fkey下标 对应关系:

Vue3源码解析之 diff(二)

下面执行第二段逻辑:

// 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] as VNode)
) {
newIndex = j
break
}
}
}
if (newIndex === undefined) {
unmount(prevChild, parentComponent, parentSuspense, true)
} else {
newIndexToOldIndexMap[newIndex - s2] = i + 1
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex
} else {
moved = true
}
patch(
prevChild,
c2[newIndex] as VNode,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
patched++
}
}

其实 Vue 注释已经写的很清楚了,该逻辑主要是遍历旧节点,尝试打补丁或者删除节点

这里 j 我们暂时先不管;patched 记录已经修复的新节点数量,比如当前还剩三个节点未修复,默认是 0toBePatched 是新节点待修复数量,当前为 3moved 为标记,代表当前节点是否需要移动;maxNewIndexSoFar 是配合 moved 是否有节点移动,保存着最大 newIndex 值;newIndexToOldIndexMap 为数组,它的下标表示新节点的下标,元素表示旧节点的下标,Vue 通过数组形式来表示 map <newIndex,oldIndex> 中数据。

另外还需注意的是,当前数组的下标是不计算已经处理好的节点。 换句话说,根据案例,第一个节点 new-a 已经处理完毕,下标是 0;而第二个节点 new-c 待处理,下标是 1。那对于 map <newIndex,oldIndex> 而言,new-c 存放时是不会计算已经处理好的节点,当前数组的下标 0 就代表 new-c 节点。

Vue3源码解析之 diff(二)

而元素为旧节点的下标,但是必须 +1(根据注释),这是为什么呢?

后续执行遍历,将 newIndexToOldIndexMap 设置默认值都为 0。这里的 0 存在特殊含义,会在第三段逻辑中使用,所以当值表示旧节点下标时就不能再设置为 0,旧节点下标就必须 +1

Vue3源码解析之 diff(二)

接着遍历旧节点,s1 为旧节点的开始下标,e1 为旧节点的结束下标,第一次遍历,此时 prevChild 当前旧节点为 b。之后根据判断 patched >= toBePatched,前面我们得知 patched 表示已经处理的节点数量,toBePatched 表示待处理的节点数量。当 patched >= toBePatched 时,就表示所有节点都处理完毕,执行 unmount 方法删除旧节点即可。当前 patched = 0toBePatched = 3 不满足条件,执行后续逻辑。

定义 newIndex 变量,表示新节点存放的位置,它需要根据旧节点来进行寻找。但是我们前面讲到 newIndexToOldIndexMap 的下标 newIndex 是不计算已经处理好的节点,而这里的 newIndex 是计算已经处理好的节点,也就是说对于 new-c 节点下标为 1,假如要将下标设置给 newIndexToOldIndexMap,需要 减1

当前旧节点 b 存在 key2,新节点下标 newIndex 通过 keyToNewIndexMap 根据旧节点 key 获取,此时为 2

Vue3源码解析之 diff(二)

旧节点 key 如果不存在,执行 else 逻辑,该逻辑是遍历所有的新节点,找到 没有找到 对应旧节点的新节点,并且该新节点可以和旧节点匹配,如果能找到,那么 newIndex = 该新节点的索引

之后判断 newIndex 是否为空,为空则表示没有找到新节点的索引,即当前旧节点没有对应的新节点,直接 unmount 删除即可,根据案例旧节点 d 存在该场景。

此时 newIndex 存在,执行 else 逻辑。我们知道 newIndexToOldIndexMap 数组下标保存的是 新节点的下标且不去计算已处理的新节点,那么怎么计算不处理的新节点呢?当前 newIndex 是计算已处理新节点的,s2 为已处理新节点的开始下标,那么 newIndex - s2 剩余的就表示未处理的新节点,value 元素 表示 旧节点下标 且永远 +1

当前 newIndex2s21 表示第一个节点 new-a 已经处理完,newIndex - s2 = 1,所以 new-c 下标为 0new-b 下标为 1newIndexToOldIndexMap[1] 就是 new-b 节点,结果为 2

Vue3源码解析之 diff(二)

Vue3源码解析之 diff(二)

maxNewIndexSoFar 会存储当前最大的 newIndex,它应该是一个递增的,如果没有递增,则证明有节点需要移动。通过上面我们分析的 最长递增子序列,不符合递增子序列的,我们就需要判断是否进行移动,移动即 moved = true

接着执行 patch 更新节点,当前旧节点为 b,新节点为 new-b,此时页面呈现:

Vue3源码解析之 diff(二)

之后下一轮遍历,旧节点 c,新节点为 new-c,此时页面呈现:

Vue3源码解析之 diff(二)

第三次遍历,newIndex 为空表示未找到新节点索引,直接删除旧节点 d,页面呈现:

Vue3源码解析之 diff(二)

下面执行第三段逻辑:

// 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] as VNode
const anchor =
nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).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, MoveType.REORDER)
} else {
j--
}
}
}

当前显示结果和原节点对比,我们发现还有些区别,new-bnew-c 节点需要移动,new-f 节点需要新增:

Vue3源码解析之 diff(二)

该逻辑主要进行移动和挂载的处理,需要配合最长递增子序列。

当前 moved = true,通过 getSequence 方法获取最长递增子序列的下标数组,即 [1]

Vue3源码解析之 diff(二)

j 的初始值是最长递增子序列最后值的下标,当前为 0。接着执行遍历,可以看出循环是倒叙的,toBePatched 表示待处理的节点。nextIndex = s2 + i 表示新节点需要更新的下标,通过下标获取当前新节点 c2[nextIndex],当前为 new-f 元素。

之后通过计算获取 anchor 锚点,nextIndex + 1 表示当前节点的后面一个节点的长度,l2 为新节点长度,nextIndex + 1 < l2 表示是否超过新节点长度,没超过锚点就为当前节点的后面一个节点,当前为 new-e 节点,表示要插入该节点前面。

接着根据判断 newIndexToOldIndexMap[i] === 0 表示新节点没有对应的旧节点,需要进行挂载操作,当前 new-f 节点未匹配到,执行挂载,此时页面呈现:

Vue3源码解析之 diff(二)

第二次循环,当前 nextChildnew-b 节点,锚点为 new-f 节点,根据判断需要执行移动逻辑。j < 0 表示不存在递增子序列,我们可以理解为:当 j 初始值最长递增子序列为 1 时,j0,当最长递增子序列为 0 时, j-1;也就是说 j 一旦小于 0,就表示最长递增子序列不存在。

i !== increasingNewIndexSequence[j] 表示当前节点不在最后位置,我们可以理解为: 当 j > 0 表示最长递增子序列最后一个下标,再用 j 获取最长递增子序列最后一个元素,如果不等于当前节点的 i,就表示当前节点不在最后位置。

根据判断执行 j--,表示当前页面未发生变化,也就是 new-b 未移动。new-b 未移动则表示 new-c 需要移动,此时页面呈现:

Vue3源码解析之 diff(二)

第三次循环,当前 nextChildnew-c 节点,锚点为 new-b 节点,此时 j = -1,不存在最长递增子序列,执行 move 方法:

const move: MoveFn = (
vnode,
container,
anchor,
moveType,
parentSuspense = null
) => {
const { el, type, transition, children, shapeFlag } = vnode
if (shapeFlag & ShapeFlags.COMPONENT) {
move(vnode.component!.subTree, container, anchor, moveType)
return
}
if (__FEATURE_SUSPENSE__ && shapeFlag & ShapeFlags.SUSPENSE) {
vnode.suspense!.move(container, anchor, moveType)
return
}
if (shapeFlag & ShapeFlags.TELEPORT) {
;(type as typeof TeleportImpl).move(vnode, container, anchor, internals)
return
}
if (type === Fragment) {
hostInsert(el!, container, anchor)
for (let i = 0; i < (children as VNode[]).length; i++) {
move((children as VNode[])[i], container, anchor, moveType)
}
hostInsert(vnode.anchor!, container, anchor)
return
}
if (type === Static) {
moveStaticNode(vnode, container, anchor)
return
}
// single nodes
const needTransition =
moveType !== MoveType.REORDER &&
shapeFlag & ShapeFlags.ELEMENT &&
transition
if (needTransition) {
if (moveType === MoveType.ENTER) {
transition!.beforeEnter(el!)
hostInsert(el!, container, anchor)
queuePostRenderEffect(() => transition!.enter(el!), parentSuspense)
} else {
const { leave, delayLeave, afterLeave } = transition!
const remove = () => hostInsert(el!, container, anchor)
const performLeave = () => {
leave(el!, () => {
remove()
afterLeave && afterLeave()
})
}
if (delayLeave) {
delayLeave(el!, remove, performLeave)
} else {
performLeave()
}
}
} else {
hostInsert(el!, container, anchor)
}
}

new-c 节点移动到 new-b 节点前面,此时页面呈现:

Vue3源码解析之 diff(二)

至此,我们所有节点都处理完毕。

总结

  1. diff 算法的第五段逻辑即 乱序比对 分为三步骤来处理。
  2. 第一步构建 keyToNewIndexMap 对象,将新节点的 key 作为 ,新节点的 下标 作为
  3. 第二步循环旧节点,尝试 打补丁 或者 删除 节点。
  4. 第三步 移动挂载 节点的处理,需要配合 最长递增子序列

Vue3 源码实现

vue-next-mini

Vue3 源码解析系列

  1. Vue3源码解析之 源码调试
  2. Vue3源码解析之 reactive
  3. Vue3源码解析之 ref
  4. Vue3源码解析之 computed
  5. Vue3源码解析之 watch
  6. Vue3源码解析之 runtime
  7. Vue3源码解析之 h
  8. Vue3源码解析之 render(一)
  9. Vue3源码解析之 render(二)
  10. Vue3源码解析之 render(三)
  11. Vue3源码解析之 render(四)
  12. Vue3源码解析之 render component(一)
  13. Vue3源码解析之 render component(二)
  14. Vue3源码解析之 render component(三)
  15. Vue3源码解析之 render component(四)
  16. Vue3源码解析之 render component(五)
  17. Vue3源码解析之 diff(一)
  18. Vue3源码解析之 diff(二)

原文链接:https://juejin.cn/post/7321569896454127627 作者:JasonChen

(0)
上一篇 2024年1月10日 下午4:53
下一篇 2024年1月10日 下午5:04

相关推荐

发表评论

登录后才能评论