Vue3.x源码阅读笔记(四)-Diff算法

之前讲过当新旧节点两个都是数组vnode的时候，就会执行我们的diff过程，也就是patchKeyedChildren方法。
我们可以回忆一下在Vue2中的diff，是通过头部和头部，尾部和尾部，头部和尾部等交叉对比来实现的，我们可以看一下在Vue3中，是如何实现的。

• 没有交叉对比，Vue3中主要是通过一个时间复杂度为O(nlogn)的求最长递增子序列来实现的。
• 可复用节点的，Vue2是老的vnode作为map,Vue3是新的vnode作为map

  // packages/runtime-core/src/renderer.ts
  const patchKeyedChildren = (
      c1, //旧的vnode
      c2, // 新的vnode
      container,
      parentAnchor,
      parentComponent,
      parentSuspense,
      isSVG,
      slotScopeIds,
      optimized
    ) => {
      let i = 0 // 索引记录
      const l2 = c2.length // 新的vnode的长度
      let e1 = c1.length - 1 // prev ending index // 旧的vnode的结尾索引
      let e2 = l2 - 1 // next ending index // 新的vnode的结尾索引
      
      while (i <= e1 && i <= e2) {
      ...
      }
      while (i <= e1 && i <= e2) { 
      ...
      }
      if (i > e1) {
        if (i <= e2) {
          ...
        }
      } else if (i > e2){
        while (i <= e1) {
          ...
        }
      }else {
          ...
      }
      ......
    }

  在diff过程中，主要会有几种情况

  1. 同步头部节点

  第一种情况就是假如以下新旧节点为这种，a、b是相同的节点，头部相同，那么就执行patch更新节点

  旧节点：(a b) c
  新节点：(a b) d e

  可以看到，声明了一个索引i为0，通过while循环，依次遍历新旧节点，通过isSameVNodeType判断是否是相同节点，如果是，那么就执行patch，不是相同节点就跳过。

  const patchKeyedChildren = (
    c1, //旧的vnode
    c2, // 新的vnode
    container,
    parentAnchor,
    parentComponent,
    parentSuspense,
    isSVG,
    slotScopeIds,
    optimized
  ) => {
    let i = 0 // 索引记录
    const l2 = c2.length // 新的vnode的长度
    let e1 = c1.length - 1 // prev ending index // 旧的vnode的结尾索引
    let e2 = l2 - 1 // next ending index // 新的vnode的结尾索引
  
    // 1. sync from start // 同步头部节点-头相同的情况
    // (a b) c
    // (a b) d e
    while (i <= e1 && i <= e2) { // 如果当前i 小于等于旧的vnode长度 并且 当前i 小于等于新的vnode长度，否则结束
      const n1 = c1[i] // 获取旧的vnode的每一个节点
      const n2 = (c2[i] = optimized // 获取新的vnode的每一个节点
        ? cloneIfMounted(c2[i] as VNode)
        : normalizeVNode(c2[i]))
      if (isSameVNodeType(n1, n2)) { // 判断新旧节点的key和type是否相等
        // 相同的节点，递归执行patch更新节点
        patch(
          n1,
          n2,
          container,
          null,
          parentComponent,
          parentSuspense,
          isSVG,
          slotScopeIds,
          optimized
        )
      } else {
        break
      }
      i++
    }
  }
    
    

  2. 同步尾部节点

  接下来就是同步尾部节点，和同步头部节点类似，这次不过是从尾部开始同步

  旧节点：a (b c)
  新节点：d e (b c)

  这里在经过同步头部节点之后，此时i = 2, e1是3，e2是4,满足while循环条件，从尾部开始，向前同步，如果相同就执行patch方法，然后新旧节点长度–，直到不满足i <= e1 && i <= e2。

  const patchKeyedChildren = (
    c1, //旧的vnode
    c2, // 新的vnode
    container,
    parentAnchor,
    parentComponent,
    parentSuspense,
    isSVG,
    slotScopeIds,
    optimized
    
  ) => {
    let i = 0 // 索引记录
    const l2 = c2.length // 新的vnode的长度
    let e1 = c1.length - 1 // prev ending index // 旧的vnode的结尾索引
    let e2 = l2 - 1 // next ending index // 新的vnode的结尾索引
    // 上面同步头部节点完成之后
    // i = 2, e1是3，e2是4
    // 2. sync from end // 同步尾部节点-尾部相同的情况。这里的e1,e2新旧节点vnode长度，都会减少--
    // a (b c)
    // d e (b c)
    while (i <= e1 && i <= e2) {  // 和上面一样
      const n1 = c1[e1] // 旧的vnode结尾
      const n2 = (c2[e2] = optimized // 新的vnode结尾
        ? cloneIfMounted(c2[e2] as VNode)
        : normalizeVNode(c2[e2]))
      if (isSameVNodeType(n1, n2)) { //  从结尾向前对比，相同的进行patch
        patch(
          n1,
          n2,
          container,
          null,
          parentComponent,
          parentSuspense,
          isSVG,
          slotScopeIds,
          optimized
        )
      } else {
        break
      }
      // 从后向前进行对比
      e1-- 
      e2--
    }
  }

  同步完成头部节点和尾部节点，剩下有几种情况处理

1. 节点有新增，新的vnode比旧的vnode多

   旧节点：(a b) 
   新节点：(a b) c
   
   
   旧节点：a b
   新节点：c (a b) 

2. 节点有删除，新的vnode比旧的vnode少

   旧节点：(a b) c
   新节点：(a b)
   
   
   旧节点：a (b c)
   新节点：(b c)

3. 未知序列，通过求最长递增子序列索引来进行计算

   3. 节点有新增

   同步完成头部节点和尾部节点之后，节点可能有新增，比如下面这种情况，可能是尾部有节点新增，也可能是头部有节点新增。此时i满足大于e1并且小于e2。

   // i = 2, e1 = 1, e2 = 2
   旧节点：(a b) 
   新节点：(a b) c
   
   // i = 0, e1 = -1, e2 = 0
   旧节点：a b
   新节点：c (a b) 

   可以看下对于这种情况的逻辑处理

   if (i > e1) {// 如果索引大于旧的vnode的结尾索引
     if (i <= e2) { // 并且，如果 i小于新的vnode的结尾索引。证明新的vnode比旧的vnode节点多，新的增加了节点，可能是头部增加也可能是尾部增加
       const nextPos = e2 + 1
       const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor
       // 这里的意思就是，因为上面两个while已经同步了头和尾，那么这里直接逻辑是新的vnode多了，直接挂载从i到e2之间的节点
       while (i <= e2) {
         patch(
           null,
           (c2[i] = optimized
            ? cloneIfMounted(c2[i] as VNode)
            : normalizeVNode(c2[i])),
           container,
           anchor,
           parentComponent,
           parentSuspense,
           isSVG,
           slotScopeIds,
           optimized
         )
         i++
       }
     }
   }

   4. 节点有删除

   如果不满足新增的逻辑，那就判断是否节点有删除的逻辑，比如这种情况

   // i = 2, e1 = 2, e2 = 1
   旧节点：(a b) c
   新节点：(a b) 
   
   // i = 0, e1 = 0, e2 = -1
   旧节点：a (b c)
   新节点：(b c)

   这种情况就直接卸载掉多余的节点。

   const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
     let i = 0
     const l2 = c2.length
     // 旧子节点的尾部索引
     let e1 = c1.length - 1
     // 新子节点的尾部索引
     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. 普通序列挂载剩余的新节点
     // i = 2, e1 = 2, e2 = 1
     // 不满足
     if (i > e1) {
     }
     // 4. 普通序列删除多余的旧节点
     // i = 2, e1 = 2, e2 = 1
     else if (i > e2) {  //如果上面逻辑相反，可能是头部删除也可能是尾部删除
       while (i <= e1) { // 直接unmount卸载掉旧的vnode节点，卸载从 i到e1之间的节点
         // 删除节点
         unmount(c1[i], parentComponent, parentSuspense, true)
         i++
       }
     }
   }

   5. 未知子序列

   这里的情况就是，在同步完成头部节点和尾部节点，中间部分不适用于简单的挂载新增或者删除。比如这种情况

   // [i ... e1 + 1]: a b [c d e] f g
   // [i ... e2 + 1]: a b [e d c h] f g
   // 同步完成头部节点和尾部节点之后的i,e1,e2分别是
   // i = 2, e1 = 4, e2 = 5

   对中间部分新老元素进行遍历，就免不了双重循环，所以需要一个降低复杂度的方法，把时间复杂度从O(n2) 降低到 O(n)。
   总体思路就是根据新节点建立的索引去查找老的是否存在，存在的话就直接patch，不存在就直接新增，多余的节点删除，需要移动的节点就移动。

   5.1 根据key建立Map索引

   在Vue2中，也以类似建立键值对，但是应该是遍历老的节点建立，这里是对新的元素遍历建立。
   我们在写v-for时候，都会写一个key，这个key就是用来建立索引图的，相同的话，就认为是一个节点。没有的话，后面会遍历所有的节点，会有一定的性能浪费。

   const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
     let i = 0
     const l2 = c2.length
     // 旧子节点的尾部索引
     let e1 = c1.length - 1
     // 新子节点的尾部索引
     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. 普通序列挂载剩余的新节点， 不满足
     // 4. 普通序列删除多余的旧节点，不满足
     // i = 2, e1 = 4, e2 = 5
     // 旧子序列开始索引，从 i 开始记录
     const s1 = i
     // 新子序列开始索引，从 i 开始记录
     const s2 = i //
     // 5.1 根据 key 建立新子序列的索引图
     const keyToNewIndexMap = new Map()
     for (i = s2; i <= e2; i++) {
       const nextChild = c2[i]
        /**
        * a b [e d c h] f g 比如上面的例子,这里的结果就是  
        * {e:2,d:3,c:4,h:5} ,假设key是字符，保存下来的结果大概就是这样
        */
       keyToNewIndexMap.set(nextChild.key, i) // 将新的vnode的key作为索引图中的key，值是i
     }
   }

   这里通过遍历新元素vnode，建立一个Map数据结构，通过set方法，将key作为Map数据的key。如同以下节点

   // [i ... e1 + 1]: a b [c d e] f g
   // [i ... e2 + 1]: a b [e d c h] f g
   // 同步完成头部节点和尾部节点之后的i,e1,e2分别是
   // i = 2, e1 = 4, e2 = 5
   // 遍历完成之后keyToNewIndexMap就是
   // keyToNewIndexMap = {e:2,d:3,c:4,h:5}

   5.2 更新和删除旧节点

   已经有了新的节点作为Map，剩下就是需要遍历老的节点，有相同的节点就patch，找不到的就删除，需要移动的就去移动。

   const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
     let i = 0
     const l2 = c2.length
     // 旧子节点的尾部索引
     let e1 = c1.length - 1
     // 新子节点的尾部索引
     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. 普通序列挂载剩余的新节点， 不满足
     // 4. 普通序列删除多余的旧节点，不满足
     // i = 2, e1 = 4, e2 = 5
     // 旧子序列开始索引，从 i 开始记录
     const s1 = i
     // 新子序列开始索引，从 i 开始记录
     const s2 = i //
     // 5.1 根据 key 建立新子序列的索引图
     // 5.2 更新和删除节点
     let j
     // 新子序列已更新节点的数量，每次更新一次，这个值会增加++
     let patched = 0
     // 新子序列待更新节点的数量，等于新子序列的长度，就像上面中括号位置里面等更新的元素个数，上面的patched增加到toBePatched，就表示更新完了
     const toBePatched = e2 - s2 + 1 // 新的vnode结尾索引-新的子序列索引+1，总的需要patch元素的数量
     // 是否存在要移动的节点
     let moved = false
     // used to track whether any node has moved
     // 用于跟踪判断是否有节点移动
     let maxNewIndexSoFar = 0
     // 这个数组存储新子序列中的元素在旧子序列节点的索引，用于确定最长递增子序列
     // 下标是新元素的相对下标，value是老元素的下标+1
     //                 0 1  2 3 4  5 6
     // [i ... e1 + 1]: a b [c d e] f g
     // [i ... e2 + 1]: a b [e c d h] f g
     // i = 2, e1 = 4, e2 = 5，比如上面这组元素，得到的结果就是[5,3,4,0],新元素第一个是e,在老节点索引是4，4+1=5
     const newIndexToOldIndexMap = new Array(toBePatched)
     
     /**
     *  初始化数组，每个元素的值都是 0
     *  0 是一个特殊的值，如果遍历完了仍有元素的值为 0，则说明这个新节点没有对应的旧节点
     */
     for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0 // 将上面的数组全部初始化为0，这里在之后的patch如果有复用会被替换成下标，否则就还是0
   
     for (i = s1; i <= e1; i++) { // 遍历旧的vnode,e1是旧的vnode的结尾索引
       const prevChild = c1[i] // c1是旧的vnode，找到第一个需要patch的元素  a b [e d c h] f g 比如说e
       if (patched >= toBePatched) { // 当前patched数量已经大于等于了toBePatched总的数量，剩下的删除
         unmount(prevChild, parentComponent, parentSuspense, true)
         continue
       }
       let newIndex
       if (prevChild.key != null) {
         // 时间复杂度O(1)
         newIndex = keyToNewIndexMap.get(prevChild.key) // 判断老的vnode在新的vnode是不是也用到了，是的话获取到当前map中的索引
       } else {
         // key-less node, try to locate a key-less node of the same type
         // 处理没有key的情况，遍历所有新的vnode节点来判断是否存在，复杂度O(n)
         for (j = s2; j <= e2; j++) {
           if (
             newIndexToOldIndexMap[j - s2] === 0 &&
             isSameVNodeType(prevChild, c2[j] as VNode)
           ) {
             newIndex = j
             break
           }
         }
       }
       // 新老节点没有找到相同的，不考虑复用，诸直接删除
       // 如果找到了，那么更新旧的vnode的索引节点
       if (newIndex === undefined) {
         // 直接卸载不能复用的旧的vnode
         unmount(prevChild, parentComponent, parentSuspense, true)
       } else {// 这里证明新老节点有可以复用的元素
         /**
         * ex: 
         * a b [c(patch) d(patch) e(patch) f(unmount)] g h
         * 
         * a b [e c d i] g h 新的vnode记录一个map
         * 最终:
         *  keyToNewIndexMap = {e:2,c:3,d:4,i:5}
         * newIndexToOldIndexMap = [5,3,4,0] // 说明节点有移动
         */
         // 更新新的vnode在在旧的vnode中的索引，+1是为了避免后续求最长递增子序列产生影响
         // newIndex - s2 这里是计算一个相对位置[e c d i]，计算相对这几个元素的相对位置
         newIndexToOldIndexMap[newIndex - s2] = i + 1 // 上面的数组记录变化
         if (newIndex >= maxNewIndexSoFar) {
           // maxNewIndexSoFar 始终存储的是上次求值的 newIndex，如果不是一直递增，则说明有移动
           /**
           * 一旦本次求值的 newIndex 小于 maxNewIndexSoFar，这说明顺序遍历旧子序列的节点在新子序列中的索引并不是一直递增的，也就说明存在移动的情况。
           */
           maxNewIndexSoFar = newIndex
         } else {
           // 节点被移动过。增加的元素不算
           // [1,2,3] 变为 [1,2,3,10]这种不会算moved = true
           moved = true
         }
         // 节点可以复用，做一次patch
         patch(
           prevChild,
           c2[newIndex] as VNode,
           container,
           null,
           parentComponent,
           parentSuspense,
           isSVG,
           slotScopeIds,
           optimized
         )
         // 每复用一次，patched++
         patched++
       }
     }
   }

   这里有两个for循环第一个是这个

   for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0 // 将上面的数组全部初始化为0，这里在之后的patch如果有复用会被替换成下标，否则就还是0

   toBePatched字面意思就是需要去patch的元素，这里是根据toBePatched=e2-s2+1计算出来的，也就是新的vnode结尾索引-新的子序列索引+1，等于总的需要patch元素的数量，我们遍历这个长度，将newIndexToOldIndexMap全部填充为0，这个数组是用来记录新旧节点对应关系的，如何来记录？看第二个for循环，首先是对旧的节点遍历，如果当前patched数量已经大于等于了toBePatched总的数量，剩下的删除。
   如果找得到，那么就更新newIndexToOldIndexMap,比如

   // old vnode
   // a b [c(patch) d(patch) e(patch) f(unmount)] g h
   // new vnode
   // a b [e c d i] g h 新的vnode记录一个map
   keyToNewIndexMap = {e:2,c:3,d:4,i:5}
   newIndexToOldIndexMap = [5,3,4,0] // 这里的就是对应old vnode中的位置

   可以看到，记录的就是对应old vnode中的位置索引，如果是0，就代表这个是新增加的元素。maxNewIndexSoFar是用来记录当前节点是否是处于递增状态，如果不是递增，那就是节点有移动，同时move也会被置为true，需要求解最长递增子序列的索引。

   5.3 移动和挂载节点

   最后是移动节点和挂载节点
   如果moved为true，那么就会getSequence求解当前最长递增子序列，比如getSequence([5,3,4,0])，就会返回[1,2]，这个里面返回的元素都不需要移动,因为3、4是递增的。

接下里就是倒叙遍历新的vnode,判断newIndexToOldIndexMap是否存在为0的情况，如果是0，就代表这个元素是新增的，直接挂载。

const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
  let i = 0
  const l2 = c2.length
  // 旧子节点的尾部索引
  let e1 = c1.length - 1
  // 新子节点的尾部索引
  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. 普通序列挂载剩余的新节点， 不满足
  // 4. 普通序列删除多余的旧节点，不满足
  // i = 2, e1 = 4, e2 = 5
  // 旧子序列开始索引，从 i 开始记录
  const s1 = i
  // 新子序列开始索引，从 i 开始记录
  const s2 = i //
  // 5.1 根据 key 建立新子序列的索引图
  // 5.2 更新和删除节点,正序遍历旧子序列，找到匹配的节点更新，删除不在新子序列中的节点，判断是否有移动节点
  // 5.3 移动和挂载新节点
  // 仅当节点移动时生成最长递增子序列
  const increasingNewIndexSequence = moved // 如果newIndexToOldIndexMap这个顺序不是递增的，表示移动过，那么就需要找出最优解
    ? getSequence(newIndexToOldIndexMap) // 获取到最长递增的子序列的索引，比如 newIndexToOldIndexMap = [5,3,4,0，这里getSequence([5,3,4,0])，就会返回[1,2]，这个里面返回的元素都不需要移动
    : EMPTY_ARR
  let j = increasingNewIndexSequence.length - 1
  // 倒序遍历以便我们可以使用最后更新的节点作为锚点
  // 这里倒循环是因为在 insert 的时候，需要保证锚点是处理完的节点（也就是已经确定位置了）
  // 因为 insert 逻辑是使用的 insertBefore()，把节点加在某一个元素前面去，需要先有最后一个节点
  for (i = toBePatched - 1; i >= 0; i--) { // toBePatched新的vnode总的需要patched数量，[e c d i],倒着开始遍历--
    const nextIndex = s2 + i // 为什么要s2+i?这里的i只是[e c d i]中的相对位置，要计算在节点中的真实位置，需要起始下标+相对下标，得到最后一个i的下标
    const nextChild = c2[nextIndex]
    // 锚点指向上一个更新的节点，如果 nextIndex 超过新子节点的长度，则指向 parentAnchor
    const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAnchor
    if (newIndexToOldIndexMap[i] === 0) { //如果当前上面记录索引的数组中有0，证明这个节点需要挂载
      // 挂载新的子节点
      patch(null, nextChild, container, anchor, parentComponent, parentSuspense, isSVG)
    }
    else if (moved) {
      // 没有最长递增子序列（reverse 的场景）或者当前的节点索引不在最长递增子序列中，需要移动
      // j小于0，因为刚开始j是increasingNewIndexSequence.length - 1 ，如果increasingNewIndexSequence.length为0，表示最长递增子序列里面没有值，就意味着没有稳定的子序列，可能是新节点这里倒序排列了，需要移动每一个值
      // 或者[5,3,4,0]遍历到5了，稳定序列getSequence([5,3,4,0])返回[1,2],5的i是0，0不在稳定序列[1,2]当中，所以需要移动
      if (j < 0 || i !== increasingNewIndexSequence[j]) {
        move(nextChild, container, anchor, 2)
      }
      else {
        // 倒序递增子序列
        j--
      }
  }
}

否则就是判断是否存在移动的元素。
j<0，意味着两种情况

• 没有递增的子序列，比如完全倒叙排序
• 当前遍历的节点索引不在稳定的子序列当中，[5,3,4,0]遍历到5了，稳定序列getSequence([5,3,4,0])返回[1,2],5的i是0，0不在稳定序列[1,2]当中，所以需要移动。

    else if (moved) {
      // 没有最长递增子序列（reverse 的场景）或者当前的节点索引不在最长递增子序列中，需要移动
      // j小于0，因为刚开始j是increasingNewIndexSequence.length - 1 ，如果increasingNewIndexSequence.length为0，表示最长递增子序列里面没有值，就意味着没有稳定的子序列，可能是新节点这里倒序排列了，需要移动每一个值
      // 或者[5,3,4,0]遍历到5了，稳定序列getSequence([5,3,4,0])返回[1,2],5的i是0，0不在稳定序列[1,2]当中，所以需要移动
      if (j < 0 || i !== increasingNewIndexSequence[j]) {
        move(nextChild, container, anchor, 2)
      }
      else {
        // 倒序递增子序列
        j--
      }
  }

  求最长递增子序列索引

// https://en.wikipedia.org/wiki/Longest_increasing_subsequence
// LIS 最长递增子序列 
// 两种解法，一种是双重for循环，复杂度On平方，另外一种就是下面这种贪心+二分
// 贪心+二分法，贪心算法的时间复杂度是 O(n)，二分查找的时间复杂度是 O(logn)，所以它的总时间复杂度是 O(nlogn)。
function getSequence(arr: number[]): number[] {
  const p = arr.slice()
  const result = [0]
  let i, j, u, v, c
  // 比如说arr = [5,3,4,0]
  const len = arr.length
  for (i = 0; i < len; i++) {
    const arrI = arr[i]
    if (arrI !== 0) { // 如果为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小的节点，更新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]
  // 回溯到数组p，找到最终的索引
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }
  return result
}