Vue3의 diff 알고리즘에 대한 심층 분석(자세한 그래픽 및 텍스트 설명)

이 글은 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  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

• diff의 주요 프로세스와 핵심 로직 code>

• diff는 노드를 재사용, 이동 및 제거하는 방법입니다

• 🎜다음과 결합할 수 있는 샘플 질문도 있습니다. 실습 분석을 위한 이 기사🎜

🎜Vnode 및 렌더러 패치 프로세스에 대해 잘 모르는 경우 다음 두 기사를 먼저 읽어 보는 것이 좋습니다. 🎜

• 🎜Vnode(https://mp.weixin.qq.com/s/DtFJpA91UPJIevlqaPzcnQ)🎜
• 🎜렌더러 분석(https://mp.weixin.qq) .com/s/hzpNGWFCLMC2vJNSmP2vsQ)🎜

1.0 diff에는 key 하위 노드가 없습니다< /h2>🎜UNKEYED_FRAGMENT를 처리하는 동안 로 표시됩니다. 🎜<ul><li>🎜먼저, 이전 및 새 자체 시퀀스를 통해 최소 공통 길이 <code>commonLength를 얻습니다. 🎜

🎜공개 부분에 대해 패치를 반복합니다. 🎜

🎜패치가 종료되고 나머지 이전 노드와 새 노드를 처리합니다. 🎜

🎜oldLength > newLength인 경우 이전 노드를 마운트 해제해야 한다는 의미입니다🎜

🎜그렇지 않으면 이는 새로운 노드가 있다는 의미입니다. 노드를 추가하려면 mount;🎜

🎜🎜🎜생략된 코드를 여기에 게시하세요. 🎜

// 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를 수행하는지, 새 노드에서 직접 mountChildren을 수행하는지(실제로는 하위 노드를 순회하여 패치를 수행하고 있기 때문입니다) 작업 ) 실제로 패치는 재귀적으로 수행되므로 성능에 영향을 미칩니다. 🎜

2.0 diff에는 key 하위 노드 시퀀스가 ​​있습니다

🎜diff에는 다음이 있습니다. < code>key가 하위 시퀀스인 경우 세분화됩니다. 주로 다음 상황 중 하나로 판단됩니다. 🎜

• 시작 위치 노드 유형은 동일합니다.
• 끝 위치 노드 유형은 동일합니다.
• 동일한 부분이 처리된 후 새 노드가 추가됩니다.
• 동일한 부분을 처리한 후에 제거해야 할 이전 노드가 있습니다.
• 시작과 끝은 같지만 중간에 재사용 가능한 비순차적 노드가 있습니다.

🎜시작 단계에서 다음과 같은 세 가지 수정 사항을 먼저 받게 됩니다: 🎜

• i = 0, 이전의 시작 위치를 가리킴 그리고 새로운 시퀀스
• e1 = oldLength - 1, 이전 시퀀스의 끝 위치를 가리킴
• e2 = newLength - 1</code >, 새 시퀀스의 끝 위치를 가리킴< /li></ul>🎜<img src="https://img.php.cn/upload/image/773/378/417/164259284096656Vue3의 diff 알고리즘에 대한 심층 분석(자세한 그래픽 및 텍스트 설명)" 제목 ="164259284096656Vue3의 diff 알고리즘에 대한 심층 분석(자세한 그래픽 및 텍스트 설명)" alt="Vue3의 diff 알고리즘에 대한 심층 분석(자세한 그래픽 및 텍스트 설명) "/>🎜<div class="code" style="position:relative; padding:0px; margin:0px;"><div class="code" style="position:relative; padding:0px; margin:0px;"><pre class='brush:php;toolbar:false;'>// 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 &gt; e2) { while (i &lt;= e1) { unmount(c1[i], parentComponent, parentSuspense, true) i++ } }</pre><div class="contentsignin">로그인 후 복사</div></div><div class="contentsignin">로그인 후 복사</div></div>🎜그럼 상황에 따라 <code>diff 처리를 시작하겠습니다. 🎜🎜2.1 시작 위치 노드 유형은 동일합니다🎜🎜🎜
  • 🎜시작 위치 유형이 동일한 노드의 경우, 오른쪽에서 diff 순회를 수행하려면 왼쪽으로 이동하세요. 🎜
  • 🎜이전 노드 유형과 새 노드 유형이 동일한 경우 패치 처리를 수행합니다🎜
  • 🎜노드 유형이 다르면 해제 및 Traverse diff🎜

  // 5. 乱序的情况
  // [i ... e1 + 1]: a b [c d e] 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)
    }
  }

  🎜에서 뛰어내립니다. 위에서 코드의 일부가 생략되었지만 기본 로직에는 영향을 미치지 않습니다. 🎜🎜순회 판단을 내리기 위해 함수의 전역 컨텍스트에서 이전에 선언된 세 개의 포인터를 사용하여 순회할 때 코드를 보면 알 수 있습니다. 🎜🎜동일한 시작 위치 i <= e1 && i <= e2까지 완전히 이동하도록 보장됩니다. 🎜🎜다양한 유형의 노드가 발견되면 diff 순회가 튀어나옵니다. 🎜🎜2.2 끝 위치 노드 유형은 동일합니다🎜🎜🎜🎜시작 위치는 diff와 동일하며 시퀀스 끝에서 즉시 종료됩니다. diff 탐색을 시작합니다. 🎜🎜이때, tail 포인터 e1, e2를 감소시켜야 합니다. 🎜

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

  🎜코드에서 볼 수 있듯이 diff 로직은 기본적으로 첫 번째와 동일하며, patch로 동일한 타입을 처리합니다. 🎜🎜다양한 유형의 break, 루프 순회 중단. 🎜🎜그리고 꼬리 포인터를 줄입니다. 🎜🎜2.3 동일한 순회 부분이 끝났습니다. 새 시퀀스에 새 노드가 있으므로 마운트하세요.🎜🎜After 위의 두 가지 상황 시작 부분과 끝 부분이 동일한 노드 처리가 패치 완료되었으며 다음 단계는 새 시퀀스의 새 노드를 패치하는 것입니다. 🎜🎜🎜🎜

  在经过上面两种请款处理之后，如果有新增节点，可能会出现 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的过程

  https://mp.weixin.qq.com/s/hzpNGWFCLMC2vJNSmP2vsQ

  在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 [c d e] 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]
  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 ，会对 <code>D、E节点进行移动。

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

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

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

  图一：

  

  图二 & 三：

  

  

  总结

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

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

  입니다. 오른쪽에서 왼쪽으로 패치된 형제 노드가 있으면 해당 형제 노드가 앵커 포인트로 사용되고, 그렇지 않으면 부모 노드가 앵커 포인트로 사용됩니다. 앵커 포인트

  newIndexToOldIndexMap[i] === 0, 새 노드가 추가되었음을 나타냅니다. 노드를 마운트해야 합니다. 이 경우 patch의 첫 번째 매개변수에 null만 전달하면 됩니다. h 노드가 먼저 패치가 될 것임을 알 수 있습니다. 그렇지 않으면 moved가 true인지 판단됩니다. 이전 분석을 통해 Node C & Node E가 전진 및 후진 변경 중에 위치가 이동했음을 알 수 있습니다. 그래서 노드는 여기로 이동될 것입니다. 이때 j는 0이고 입니다. i 이때 **2**이고, i !== 증가NewIndexSequence[j]는 true입니다. > C 노드는 이동하지 않고 대신 j--를 실행합니다.

  나중에 j 이기 때문에 <code>D 및 E 노드가 이동됩니다. 🎜이 시점에서 Vue3 diff 알고리즘에 대한 학습 및 분석이 완료되었습니다. 🎜🎜다음은 실습을 위해 이 기사의 분석 과정과 결합할 수 있는 모든 사람을 위한 예입니다. 🎜🎜분석을 위해 첫 번째 그림만 볼 수 있으며, 분석 후에는 두 번째 및 세 번째 그림과 비교할 수 있습니다. 영화. 🎜🎜그림 1: 🎜🎜🎜🎜그림 2 & 3: 🎜🎜🎜🎜🎜

  요약

  🎜위의 학습 분석을 통해 Vue3의 diff 알고리즘은 먼저 동일한 노드에서 patch 처리를 수행하고 완료 후 새 노드가 마운트되고 이전 노드가 제거됩니다. 🎜🎜고장 등 서브시퀀스의 상황이 더 복잡한 경우 재사용 가능한 노드를 먼저 찾은 후 재사용 가능한 노드의 위치 매핑을 통해 최대 증가 서브시퀀스를 구성하고 최대 증가 서브시퀀스는 노드를 마운트 및 이동합니다. diff 효율성을 개선하고 노드 재사용 가능성을 극대화합니다. 🎜🎜【관련 추천: 🎜vue.js tutorial🎜】🎜

  위 내용은 Vue3의 diff 알고리즘에 대한 심층 분석(자세한 그래픽 및 텍스트 설명)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!