首页  >  文章  >  web前端  >  深入解析Vue3中的 diff 算法(图文详解)

深入解析Vue3中的 diff 算法(图文详解)

青灯夜游
青灯夜游转载
2022-01-19 19:57:403805浏览

本篇文章带大家通过图文来深入解析下Vue3中的 diff 算法,希望对大家有所帮助!

深入解析Vue3中的 diff 算法(图文详解)

本篇文章主要分析Vue3 diff算法,通过本文你可以知道:

  • diff的主要过程,核心逻辑

  • diff是如何进行节点复用、移动、卸载

  • 并有一个示例题,可以结合本文进行练习分析

如果你还不是特别了解Vnode、渲染器的patch流程,建议先阅读下面两篇文章:

  • Vnode(https://mp.weixin.qq.com/s/DtFJpA91UPJIevlqaPzcnQ)

  • 渲染器分析(https://mp.weixin.qq.com/s/hzpNGWFCLMC2vJNSmP2vsQ)

1.0  diffkey子节点

在处理被标记为UNKEYED_FRAGMENT时。

  • 首先会通过新旧自序列获取最小共同长度commonLength

  • 对公共部分循环遍历patch

  • patch 结束,再处理剩余的新旧节点。

  • 如果oldLength > newLength,说明需要对旧节点进行unmount

  • 否则,说明有新增节点,需要进行mount;

1.png

这里贴下省略后的代码。

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 diffkey子节点序列

diffkey子序列的时候,会进行细分处理。主要会经过以下一种情况的判断:

  • 起始位置节点类型相同。
  • 结束位置节点类型相同。
  • 相同部分处理完,有新增节点。
  • 相同部分处理完,有旧节点需要卸载。
  • 首尾相同,但中间部分存在可复用乱序节点。

在开始阶段,会先生面三个指正,分别是:

  • i = 0,指向新旧序列的开始位置
  • e1 = oldLength - 1,指向旧序列的结束位置
  • e2 = newLength - 1,指向新序列的结束位置

2.png

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 起始位置节点类型相同

3.png

  • 对于起始位置类型相同的节点,从左向右进行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 3f8632266e0ee97c29adb9df93ff2933  e1 && i 0898b43d16c834467d59a9467bf189b4 e2 && i 1e7b803c6ca2c6b778cb1a34be2cc477= 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的同时,会通过判断newIndexmaxNewIndexSoFa的关系,确定节点是否发生移动。

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]的最大递增子序列。

10.png

已上图为例,在未处理的乱序节点中,存在新增节点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--
    }
  }
}

11.png

从上面的代码可以知道:

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

至此我们就完成了Vue3 diff算法的学习分析。

这里为大家提供了一个示例,可以结合本文的分析过程进行练习:

可以只看第一张图进行分析,分析结束后可以与第二三张图片进行对比。

图一:

12.png

图二 & 三:

13.png

14.png

总结

通过上面的学习分析,可以知道,Vue3diff算法,会首先进行收尾相同节点的patch处理,结束后,会挂载新增节点,卸载旧节点。

如果子序列的情况较为复杂,比如出现乱序的情况,则会首先找出可复用的节点,并通过可复用节点的位置映射构建一个最大递增子序列,通过最大递增子序列来对节点进行mount & move。以提高diff效率,实现节点复用的最大可能性。

【相关推荐:vue.js教程

以上是深入解析Vue3中的 diff 算法(图文详解)的详细内容。更多信息请关注PHP中文网其他相关文章!

声明:
本文转载于:juejin.cn。如有侵权,请联系admin@php.cn删除