Array -> Array的几种情况
6.1 左侧对比
- happy patch
- 实现左侧对比的逻辑
6.2 右侧对比
- happy patch
- 实现右侧对比
6.3 diff算法 - 创建节点
6.4 diff 算法 - 删除节点
- 左侧一样，老的Array的比新的Array长 - 删除老节点
- 右侧一样，老的Array的比新的Array长 - 删除老节点
6.5 diff 算法 - 中间对比

这里实现 Element更新中 children为 Array -> Array 的逻辑

Array1 -> Array2 之前的对比，不单单考虑删除老的 Array, 创建新的 Array而已，需要考虑更过的场景来适配 Element 的更新，因为在前端领域中，往往页面中数据发生的改变，都是Element 节点中间的一小部分。
例如

Element 节点中，只有一个数据发生变化，不可能遍历全部Array来查找改变的数据，这样开销太大，性能也不行

所以Vue实现的 diff 算法，用于适配 Element更新场景，找出Element 中发生的改变，进行Element 的更新

Array -> Array的几种情况

使用双端对比算法 Array -> Array
双端对比算法的核心：就是筛选出两个 Array 中间的乱序元素

6.1 左侧对比

1. 左侧
- Array1: A B C
- Array2: A B D E
- 找出左侧相同的元素，即 A B，得到乱序的元素 D E ，然后基于乱序元素进行对比，确定要改变的元素 C -> D E

happy patch

/* ArrayToArray.js*/
// 1. 左侧对比
// ( A B ) C
// ( A B ) D E
const prevChildren = [
  // 多谢了一个 Key
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
];
const nextChildren = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "E" }, "E"),
];
// 导出手动改变的的组件
export default {
  name: "ArrayToArray",
  setup() {
    // 定义响应式变量
    const isChange = ref(false)
    window.isChange = isChange
    return {
      isChange
    }
  },
  render() {
    const self = this
    // 实现根据 isChange 判断显示的 节点
    return self.isChange === true ? h("div", {}, nextChildren) : h("div", {}, prevChildren)
  }
};

接上节 Element 更新的变化， Array -> Array 的逻辑

/* renderer.ts */
/* 其他代码 */
if (shapeFlag & ShapeFlags.TEXT_CHILDREN){
  // 其他代码
} else { // 更新后的节点是一个 Array
  if (prevShapeFlag & ShapeFlags.TEXT_CHILDREN) {
    // Text -> Array
    // 1. 把Text清空
  }else {
    // Array -> Array 
    // 老Array -> 新Array
    // 使用 patchKeyChildren 函数实现
    // 传入 老的 Array 和 新的 Array, container, parentComponet 之后patch()渲染函数会需要
    patchKeyChildren(c1, c2, container, parentComponet)
  }
}

实现左侧对比的逻辑

实现对左侧对比的思路


实现思路： 
1. 基于指针 i  e1  e2 
 - 其中 i 指针为 0 ， 指向两个数组的头部 
 - e1  为 老节点的 尾指针,  值为 e1 = n1.children.length - 1  Array1 的元素个数 
 - e2  为新节点的 尾指针， 值尾 e2 = n2.children.length - 1  Array2 的元素个数
2. 基于左侧对比， n1.children [i]  于 n2.children [i] 比较
  - 左侧元素相同， 把 i 指针向后一个位 移动  i++
  - 当两个Array元素不同时，i 指针停止，得到 i 的值
3. 根据 得到 i  e1  e2 判断大小，并且确定变化的节点，确定Array是 增加 | 删除 | 修改 | 移动
 - 这里 左侧对比 位创建 D E 节点
 - 基于指针的判断 i <= e1 && i <= e2
 - 调用 patch() 进行创建 渲染

实现左侧对比

/* renderer.ts */
// Array -> Array : diff 算法的逻辑 
function patchKeyChildren(c1, c2, container, parentComponet) {
  /**
     * 1. 左侧对比
     * ( A B ) C
     * ( A B ) D E
     * 
     * 实现思路： 
     * 1. 基于指针 i  e1  e2 
     *  - 其中 i 指针为 0 ， 指向两个数组的头部 
     *  - e1  为 老节点的 尾指针,  值为 e1 = n1.children.length - 1  Array1 的最后一个节点元素 
     *  - e2  为新节点的 尾指针， 值尾 e2 = n2.children.length - 1  Array2 的最后一个节点元素 
     * 
     * 2. 基于左侧对比， n1.children [i]  于 n2.children [i] 比较
     *   - 左侧元素相同， 把 i 指针向后一个位 移动  i++
     *   - 当两个Array元素不同时，i指针停止，得到 i 的值
     * 
     * 3. 根据 得到 i  e1  e2 判断大小，确定Array是 增加 | 删除 | 修改 | 移动
     *  - 这里 左侧对比 位创建 D E 节点
     *  - 调用 patch() 进行创建 渲染
     */
  // 1. 创建 i  e1  e2 指针索引 
  let i = 0;   // 指向两个数组的头部
  let e1 = c1.length - 1  // 老节点 Array1 的最后一个节点元素 
  let e2 = c2.length - 1 // 新节点 Array2 的最后一个节点元素
  // 左侧对比 
  // 2. 循环对比
  while(i <= e1 && i <= e2) {  // 因为 i 不可能 大于 e1 e2 ， 只能在 e1 e2 这个范围内遍历
    // 取出节点 
    const n1 = c1[i]
    const n2 = c2[i]
    // 实现判断 n1 n2 是否一样的函数
    function isSomeVNodeType(n1, n2) {
      // 基于 key  ||  type 判断 两个节点是否相同 
      return n1.type === n2.type && n1.key === n2.key 
    }
    // 判断连个节点
    if (isSomeVNodeType(n1, n2)) {
      // 如果相同, 调用 patch() 函数，进行更深层次的对比 
      patch(n1, n2, container, parentComponent)
    }else {
      // 如果 n1 n2 不同 
      // 退出循环, 然后 i++
      break
    }
    // 移动 i 的指针
    i++
  }
  // 查看 i 的指针, 根据 DEMO 左侧对比完 i 的值应该为 2 
  console.log(i)
}

在虚拟节点中初始化 key

/* vnode.ts */
const vnode = {
  // 初始化 key
  key: props && props.key,
}

到此就完成了左侧的对比，主要的逻辑是算出指针 i ，算出不同节点时的指针；才根据指针进行之后的创建、删除等逻辑

6.2 右侧对比

右侧
- Array1: A B C
- Array2: D E B C
- 基于右侧找到形同的元素 B C , 得到乱序的元素 A D E , 然后基于乱序元素进行对比，确定要改变的元素 A -> E D

happy patch

/* ArrayToArray.js */
// 2.右侧对比
//  A ( B  C )
//  D E (B C )
const prevChildren = [
  // 多谢了一个 Key
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
];
const nextChildren = [
  h("p", { key: "D" }, "D"),
  h("p", { key: "E" }, "E"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
];
// 其他代码

抽离 isSomeVNodeType() 判断节点相同的方法，因为之后代码都需要用

/* renderer.ts*/
function patchKeyedChildren(c1, c2, container, parentComponent) {
  let i = 0 
  let e1 = c1.length - 1 
  let e2 = c2.length - 1 
  function isSomeVNodeType(n1, n2) {
    // 基于 key || 基于 VNode.type 判断两个节点的不同 
    return n1.type === n2.type && n1.key === n2.key
  }
}

实现右侧对比

实现思路

1. 基于指针 i  e1  e2
  - 基于指针的判断 i <= e1 && i <= e2 , 因为  i 只能在这个范围
2. 循环 n2 n2 对比 
  - i 初始为 0, 因为是左侧对比，i 基本固定不动 
  - 当 n1 n2 形同时， 移动 e1 e2  -> e1--, e2-- 
  - 当 n1 n2 不同时， 得到变化的节点，和 e1 e2 变化的值
3. 根据 得到 i  e1  e2 判断大小，确定Array是 增加 | 删除 | 修改 | 移动
  - 这里 右侧对比 为 删除 A ，创建 D E 节点

代码实现

/* renderer.ts */
function patchKeyedChildren(c1, c2, container, parentComponent) {
  let i = 0  //  指向两个数组的头部
  let e1 = c1.length - 1  // 老节点 Array1 的最后一个节点 
  let e2 = c2.length - 1  // 新节点 Array2 的最后一个节点
  function isSomeVNodeType(n1, n2) {
    // 基于 key || 基于 VNode.type 判断两个节点的不同 
    return n1.type === n2.type && n1.key === n2.key
  }
  // 其他代码
  // 2.右侧对比
  //  A ( B  C )
  //  D E (B C )
  /**
     * 1. 基于指针 i  e1  e2
     *   - 基于指针的判断 i <= e1 && i <= e2 , 根左侧逻辑一样， i 只能在这个范围
     * 2. 循环 n2 n2 对比 
     *  - i 初始为 0, 因为是左侧对比，i 基本固定不动 
     *  - 当 n1 n2 相同时， 移动 e1 e2  -> e1--, e2-- 
     *  - 当 n1 n2 不同时， 得到变化的节点，和 e1 e2 变化的值
     * 
     * 3. 根据 得到 i  e1  e2 判断大小，确定Array是 增加 | 删除 | 修改 | 移动
     * - 这里 右侧对比 为 删除 A ，创建 D E 节点
     * 
     * 4. 基于当前 Array 最后的出 i = 0 && e1 = 0 e2 = 1  -> 确认变化的范围
     */
  // 2.1 循环对比 
  while (i <= e1 && i <= e2) {
    // 2.2 取出右侧的节点
    const n1 = c1[e1]
    const n2 = c2[e2]
    // 判断
    if (isSomeVNodeType(n1, n2)) {
      // 2.3. 如果相同，调用 patch() 递归进行对比
      patch(n1, n2, container, parentComponent)
    } else {
      // 如果不同时，退出循环
      break
    }
    // 2.4 移动 e1 e2
    e1--
    e2--
  }
  // 查看 i e1 e2 的值; 根据DEMO i = 0  | e1 = 0 | e2 = 1
  console.log(i, e1, e2)
}

6.3 diff算法 - 创建节点

左侧一样，新的Array比老的Array长 - 创建新节点

组件测试

/*example/update/patchChildren/ArrayToArray.js */
// 对比场景
// 3 左侧一样， 新的比老的长  -> 创建节点
const prevChildren = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
];
const nextChildren = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
];

实现创建节点的逻辑

/**
* 对比场景 
* 
* 1. 左侧一样， 新的比老的长 
*  - Array1: A B 
*  - Array2: A B C
*  - Array2: A B C D
*  - 基于左侧对比，得到变化的元素，创建 C ， 把新创建的 C 添加到尾部
* 
* 实现对比-> 创建 C 节点 
* 1. 两个Array 进行对比， 因为是左侧一样， 新的比老的长，多出了 C 节点
* 2. 基于指针 i  e1  e2 , 确定 C节点的位置 
* 3. 创建 C 节点 添加到 Array2 尾部 
*
*    - 最后指针为 i = 1  |  e1 = 1 | e2 = 2  
*    - 创建 C 节点，添加到 Array2 尾部
*    - 所以 当i > e1  && i <= e2 时创建节点
* 
 */

代码实现

/* renderer.ts */
function patchKeyedChildren(c1, c2, container, parentComponent) {
  let i = 0  //  指向两个数组的头部
  let e1 = c1.length - 1  // 老节点 Array1 的最后一个节点 
  let e2 = c2.length - 1  // 新节点 Array2 的最后一个节点
  function isSomeVNodeType(n1, n2) {
    // 基于 key || 基于 VNode.type 判断两个节点的不同 
    return n1.type === n2.type && n1.key === n2.key
  }
  // 其他代码
  /**
     * 3. 左侧一样， 新的比老的长, 进行创建节点 
     *  - Array1: A B 
     *  - Array2: A B C D
     *  - 基于左侧对比，得到变化的元素，创建 C ， 把新创建的 C 添加到尾部
     * 
     * 实现对比-> 创建 C 节点 
     * 1. 两个Array 进行对比， 因为是左侧一样， 新的比老的长，多出了 C 节点
     * 2. 基于指针 i  e1  e2 , 确定 C节点的位置 
     * 3. 创建 C 节点 添加到 Array2 尾部 
     * 
     *    - 最后指针为 i = 1  |  e1 = 1 | e2 = 2  
     *    - 创建 C 节点，添加到 Array2 尾部
     *    - 所以 i > e1  && i <= e2 时创建节点
     * 
     */
  if (i > e1) {
    if ( i <= e2) {
      // i > e1  && i <= e2 时创建节点 -> 因为确定 新Array 比老 Array 长
      // 调用 patch() 进行创建 
      // 因为左侧对比到不同时，C 节点时， n1 是没有值的， n2 就是需要创建的新节点
      // 把创建的节点 C 添加到尾部 
      patch(null, c2[i], container, parentComponent)
    }
  }
}

效果图，创建 C 节点

右侧一样，新的Array比老的长Array - 创建新节点

组件逻辑


// 4. 右侧一样， 新的比老的长
const prevChildren = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
];
const nextChildren = [
  h("p", { key: "C" }, "C"),
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
];

实现思路


2. 右侧一样， 新的比老的长  -- 创建新节点逻辑 
- Array1: A B
- Array2: C A B
- 基于右侧对比，得到变化的元素， 创建 C ，把新创建的 C 添加到头部
实现对比-> 创建 C 节点
1. 两个Array 进行对比，基于右侧对比， 因为是右侧一样， 新的比老的长，多出了 C 节点
2. 基于指针 i  e1  e2 , 确定 C节点的位置
3. 创建 C 节点 添加到 Array2 头部
- 右侧进行对比完，最后的指针为 i = 0 | e1 = -1 | e2 = 0
- 所以在 i > e1  && i <= e2 时 创建新的节点 
- 创建 C 节点，添加到 Array2 头部 ， 指定的位置
- 实现添加到头部需要 ： 锚点 -> 基于锚点 把创建的节点添加锚点的前一位置

代码实现

/*renderer.ts*/
    /**
     *  4. 右侧一样， 新Array的比老Array的长 - 创建节点
     *  - Array1:   A B
     *  - Array2: C A B
     *  - 基于右侧对比，得到变化的元素， 创建 C ，把新创建的 C 添加到头部
     * 
     * 实现对比-> 创建 C 节点
     *  1. 两个Array 进行对比，基于右侧对比， 因为是右侧一样， 新的比老的长，多出了 C 节点
     *  2. 基于指针 i  e1  e2 , 确定 C节点的位置
     *  3. 创建 C 节点 添加到 Array2 头部
     * 
     *  - 右侧进行对比完，最后的指针为 i = 0 | e1 = -1 | e2 = 0
     *  - 所以在 i > e1  && i <= e2 时 创建新的节点 
     *  - 创建 C 节点，添加到 Array2 头部 ， 指定的位置
     *      - 实现添加到头部需要 ： 锚点 -> 基于锚点 把创建的节点添加锚点的前一位置 
     */
    // 因为 左侧和右侧一样， 判单创建节点，指针的的值范围都一样， 进行合并写 
    if (i > e1) {
      if (i <= e2) {
        // i > e1  && i <= e2 时创建节点 -> 因为确定 新Array 比老 Array 长，所以需要创建节点 
        // 调用 patch() 进行创建 
        // 因为左侧对比到不同时，C 节点时， n1 是没有值的， n2 就是需要创建的新节点
        // 把创建的节点 C 添加到尾部 
        // patch(null, c2[i], container, parentComponent)
        // 声明一个锚点， 锚点等于 A 节点的 el , 把创建的节点 添加打A节点前 
        // 声明一个 位置  nextPos
        const nextPos = i + 1 // 因为右侧对比，i 一直为0;  i+1 就是就是获取锚点的位置 
        // 因为这里的逻辑时 左侧对比 & 右侧对比 新节点比老节点长。 的逻辑都会执行这里 
        // 所以需要设置一个锚点，根据锚点判断，是添加在 头部 还是 尾部
        const anchor = i + 1 > c2.length ? null : c2[nextPos].el
        // 分析： 判断 i + 1 > c2.length  新节点的元素个数, 如果大于那就是进行了左侧对比， 所以赋值锚点为 null ， 表示添加到最后的尾部位置 
        //  如果 i + 1 没有大于 新节点的元素个数， 说明进行的是右侧对比，赋值锚点为 c2[i+1].el， 新节点的第二个位置的元素 ： A ，就是锚点, 
        // 给 patch 函数 赋值锚点
        patch(null, c2[i], container, parentComponent, anchor)
      }
    }

renderer.ts patch() 新增描点

/* renderer.ts */ 
// 把锚点赋值为 null， 因为初始时候
patch(null, vnode, container, null, null);
function patch(n1, n2, container, parentComponent, anchor) {
  ...
}
  // 其他需要 patch() 的函数都需要加上 anchor 描点
  // 在mountElement 时， 添加到容器
  function mountElement(vnode, container, parentComponent, anchor) {
    // 4. 挂载 el 到 容器 container 上
    // container.appendChild(el)
    // 接口3 insert()
    // 添加到容器
    hostInsert(el, container, anchor);
  }

在 runtime-dom 中 insert() 增加描点

// 添加 anchor 锚点
function insert(child, parent, anchor) {
  // 基于 DOM 实现的
  // parent.append(el)
  // 添加节点到执行位置之前 beforeinsert() 
  // 这里设置 默认锚点的位置为 null, 如果没有传值，默认为 null， 也就是默认添加到最后， 和append 一样
  parent.insertBefore(child, anchor || null)
}

效果预览

修复 bug

bug 出现的原因： 
 Array1: A B
 Array2: D C A B
 这里出现 bug, 当新的 Array 创建多个节点时，C  D , 会出现问题，它会添加到最后，而不是头部
 - 分析： 当进行右侧对比后： i = 0 | e1 = -1 | e2 = 1 , 然后进入到创建的逻辑。
         但是在设置 nextPos = i + 1， 指定到C节点，而此时C节点还没有创建， 所以 nextPos = null
 - 解决： 应该获取锚点是是基于 e2 + 1 -> 取到 A 节点
 这样创建节点时基于锚点 A，在A前面插入 D 节点 ->  在A前面插入 C 节点

在获取新Array2 的头部节点（描点）时，改为 e2 + 1 , 并且增加循环创建多个节点的逻辑

/* renderer.ts */
if (i > e1) {
  if (i <= e2) {
    const nextPos = e2 + 1  // 修改 bug ： 改为 使用  e2 + 1 获取到 Array2 创建时 A 的描点
    const anchor = nextPos < l2 ? c2[nextPos].el : null  // 改为 nextPos 判断左右的对比，
    // 因为创建的节点， 不仅仅是一个, 可能还有 C D
    // 循环一个 循环 , 进行创建
    while (i <= e2) {
      // 给 patch 函数 赋值锚点
      patch(null, c2[i], container, parentComponent, anchor)
      // 创建玩当前节点后，把 i 指针向后移动一位 
      i++
    }
  }
}

6.4 diff 算法 - 删除节点

左侧一样，老的Array的比新的Array长 - 删除老节点

测试组件

/* example/update/patchChildren/ArrayToArray.js */
// 当老的Array 比 新的 Array长时 ,  -> 进行删除逻辑
// 5. 基于左侧对比 -> Array1 比 Array2 长 执行删除 老节点逻辑 
const prevChildren = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
];
const nextChildren = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
];

实现逻辑

执行删除的逻辑
左侧对比 Array1 比 Array2  执行删除 老节点逻辑 
 * 3. Array1 比 Array2 长 
 *  - Array1: A B C 
 *  - Array2: A B
 *  - 基于左侧对比，  找到乱序元素 C ,  执行删除 C 
 * 
 * 实现： 
 *  1. 两个Array 进行对比，基于左侧对比， 因为是左侧一样，老的比新的长，多出了 C 节点，所以需要删除 C 节点
 *  2. 在进行左侧对比时， 基于指针 i  e1  e2 , 确定 C节点的位置
 *  3. 最后指针为 i = 2 | e1 = 2 | e2 = 1  , 确定多出了 C 节点
 *  4. 执行删除 C 节点
 * 
 *    - 进行判断删除的逻辑 
 *    - i > e2 && i <= e1 时，执行删除逻辑 （主要是 i > e2 && i <= e1））
 *    - 删除 C 节点

在patchKeyedChildren 逻辑中操作节点的逻辑 , 中增加判断

/* renderer.ts */
    if (i > e1) {
      if (i <= e2) {
       // 创建节点逻辑 
      }
    } else if (i > e2) {  // 增加判断逻辑 
      // 执行删除的逻辑 
      // 左侧对比 Array1 比 Array2  执行删除 老节点逻辑 
      /**
       * 3. Array1 比 Array2 长 
       *  - Array1: A B C 
       *  - Array2: A B
       *  - 基于左侧对比，  找到乱序元素 C ,  执行删除 C 
       * 
       * 实现： 
       *  1. 两个Array 进行对比，基于左侧对比， 因为是左侧一样，老的比新的长，多出了 C 节点，所以需要删除 C 节点
       *  2. 在进行左侧对比时， 基于指针 i  e1  e2 , 确定 C节点的位置
       *  3. 最后指针为 i = 2 | e1 = 2 | e2 = 1  , 确定多出了 C 节点
       *  4. 执行删除 C 节点
       * 
       *    - 进行判断删除的逻辑 
       *    - i > e2 && i <= e1 时，执行删除逻辑 （主要是 i > e2 && i <= e1））
       *    - 删除 C 节点
       */
      // 循环删除
      while (i <= e1) {
        // 执行删除多出的节点 c1[i].el  使用 hostRemove 接口删除 
        hostRemove(c1[i].el)
        // 移动 i 的指针
        i++
      }
    } else {
      // 乱序的部分， 中间的部分
    }

右侧一样，老的Array的比新的Array长 - 删除老节点

组件模拟

/* example/update/patchChildren/ArrayToArray.js */
// 当老的Array 比 新的 Array长时 ,  -> 进行删除逻辑
// 6. 基于右侧对比 
const prevChildren = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
];
const nextChildren = [
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
];

实现逻辑

4. Array1 比 Array2 长
 - Array1: A B C
 - Array2: B C
 - 基于左侧对比， 得到变化的元素 A ，  执行删除 A 
- 基于右侧对比， 得到指针数据， i = 0 | e1 = 0 | e2 = -1
- 发现于左侧对比，实现的判断一样  i <= e1 ; i > e2 ， 执行删除逻辑 
- 删除 首部节点 A

所以不需要写代码，实现的基本和左侧对比删除一样

6.5 diff 算法 - 中间对比

// 两个Array 中间 进行对比 
 双端对比中， 最复杂的中间元素的对比，  也是 双端对比的最核心部分
 中间元素乱序的几种情况
 Array1:  A B C Y E F G
 Array2:  A B E D C F G
 中间乱序： C Y E  -> E D C 
 1. 创建新的 D  -> 老的节点中不存在， 新的节点中存在
 2. 删除老的节点中 Y  ->  在老节点的里面存在， 新节点里面不存在
 3. 移动 C E  ->  节点存在于新的和老的节点里， 但是位置发生改变了

6.5.1 中间对比 - 删除老节点

组件测试代码

/* example/update/patchChildren/ArrayToArray.js */
const prevChildren = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C", id: "c-prev" }, "C"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "F" }, "F"),
  h("p", { key: "G" }, "G"),
];
const nextChildren = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "E" }, "E"),  // 增加了E节点 & 删除 D 节点
  h("p", { key: "C", id: "c-next" }, "C"),  // props不同
  h("p", { key: "F" }, "F"),
  h("p", { key: "G" }, "G"),
];

实现中间乱序节点，删除的逻辑

// 1. 删除Array2 中的节点 D  -> 老节点中存在， 新节点中不存在 （移动|创建先不实现）
 Array1:  A B C D F G
 Array2:  A B E C F G
 在Array1 和 Array2 已经进行过双端对比，得到中间节点的不同， 乱序的节点
    - C  D 
    - E  C
    - 删除 D  并且创建 E
 实现思路：找到中间乱序的节点， 进行遍历一遍 -> 在新Array2中创建映射表，遍历老Array1, 根据映射表，删除映射表的节点 -> D 节点
         - 还有一种遍历方法，也就是通过 key 查找节点。 -> 新节点key 是否在老节点 key 里面 
 1. 经过左侧与右侧的对比，得到中间节点的不同， 乱序的节点
    - 此时的指针为 i = 2 | e1 = 3 | e2 = 3
 2. 创建 基于新Array2映射表, key -> value, key 就是节点的key, value 为节点的索引值 
 3. 老节点遍历，根据key 查找对应的映射表, 如果没有对应上，就删除老Array1中 节点-> D 节点
     - 如果查找到对应的 映射表，调用 patch() 进行对比，可以 props | children不同需要进行修改

具体代码实现

/* renderer.ts*/
{
  // 其他代码 
} else {
  // 乱序的部分， 中间的部分
  // 1. 删除Array2 中的节点 D  -> 老节点中存在， 新节点中不存在 （移动|创建先不实现）
  /**
   * Array1:  A B C D F G
   * Array2:  A B E C F G
   * 
   * 
   * 
   * 在Array1 和 Array2 已经进行过双端对比，得到中间节点的不同， 乱序的节点
   *    - C  D 
   *    - E  C
   *    - 删除 D  并且创建 E
   * 
   * 实现思路：找到中间乱序的节点， 进行遍历一遍 -> 在新Array2中创建映射表，遍历老Array1, 根据映射表，删除映射表的节点 -> D 节点
   *         - 还有一种遍历方法，也就是通过 key 查找节点。 -> 新节点key 是否在老节点 key 里面 
   * 
   * 1. 经过左侧与右侧的对比，得到中间节点的不同， 乱序的节点
   *    - 此时的指针为 i = 2 | e1 = 3 | e2 = 3
   * 2. 创建 基于新Array2映射表, key -> value, key 就是节点的key, value 为节点的索引值 
   * 3. 老节点遍历，根据key 查找对应的映射表, 如果没有对应上，就删除老Array1中 节点-> D 节点
   *     - 如果查找到对应的 映射表，调用 patch() 进行对比，可以 props | children不同需要进行修改 
   */
  // 此时的指针为 i = 2 | e1 = 3 | e2 = 3
  // 1. 需要遍历 Array1 和 Array2 中间乱序的部分
  // 创建指针 
  let s1 = i  // 老Array1 中间乱序的部分，开始遍历的位置 
  let s2 = i // 新 Array2 中间乱序的部分，开始遍历的位置 
  // 2. 基于 新Array2 创建映射表， 存储Array2 中间乱序的节点部分
  const keyToNewIndexMap = new Map<string, number>()
  for (let i = s2; i <= e2; i++) {
    // 获取到当前节点 
    const nextChild = c2[i]
    // 添加到映射表中， key -> value , key 就是节点的key, value 为节点的索引值
    keyToNewIndexMap.set(nextChild.key, i)
  }
  // 定义一个遍历，保存 Array1 节点 在 Array2 中的位置 
  let newIndex
  // 3. 遍历 Array1 中间乱序的部分 
  for (let i = s1; i <= e1; i++) {
    // 获取到 Array1 当前的节点 
    const prevChild = c1[i]
    // 判断 Array1 当前节点 的属性是否具有key
    // 当前节点 没有key， 那么key就有两种 情况 null | undefined  
    if (prevChild.key !== null) {
      // 当有key 时，才会去判断是否在映射表中， 因为映射表基于 Array2 乱序节点 key 创建的
      // 根据在老Array 真正遍历的节点 key,  查找对应的映射表
      // 如果能获取到值 -> 新Array2中 一定存在该节点
      // 如果没有 -> 说明该节点在新Array2中不存在，需要删除
      newIndex = keyToNewIndexMap.get(prevChild.key)  // 返回索引值， 新节点所在位置 
      // 当 key 没有时 newIndex 为 undefined
    } else {
      // 如果没有 当前节点 没有设置 key 
      // 遍历 新Array2 中的节点，对比 Array1 中的节点, 判断是否存在
      // 如果不相同，删除老节点
      for (let j = s2; i <= e2; i++) {
        // 判断 新老节点是否相同 
        if (isSomeVNodeType(prevChild, c2[j])) {
          // 进行 newIndex 赋值 -> 新节点所在的位置
          newIndex = j
          // 查找到节点， 就没有必要遍历了
          break
        }
      }
    }
    // 4. 基于 newIndex索引，判断节点的状态 
    // 判断 newIndex 是否存在
    if (newIndex === undefined) {
      // 如果没有取到值 -> undefined，说明该节点在新Array2中不存在，需要删除
      // 删除老节点 ，也就是当前节点
      hostRemove(prevChild.el)
    } else {
      // 如果 newIndex 具有值 -> 新节点所在的位置
      // 调用patch() 进行更深度的对比 -> 进行判断 props | children 这些属性 
      patch(prevChild, c2[newIndex], container, parentComponent, null)
    }
  }
}

完成删除中间乱序的的节点 - (E 还没有创建)

优化删除的逻辑

/* example/update/patchChildren/ArrayToArray.js */
const prevChildren = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C", id: "c-prev" }, "C"),
  // 新增了 E 节点
  h("p", { key: "E" }, "E"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "F" }, "F"),
  h("p", { key: "G" }, "G"),
];
const nextChildren = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "E" }, "E"),  // 增加了E节点 & 删除 D 节点
  h("p", { key: "C", id: "c-next" }, "C"),  // props不同
  h("p", { key: "F" }, "F"),
  h("p", { key: "G" }, "G"),
];

优化思路


// 2. 优化删除逻辑
* Array1:  A B C E D F G
* Array2:  A B E C F G
*  
* - i = 2 | e1 = 4 | e2 = 3
* 优化的点： 当遍历Array1, 对应映射表时，如果映射表中的项已经映射完了，
  就不再进行循环映射了，直接删除Array1 之后的节点
* 实现：
* 1. 记录新Array 变化的数量， 当每次映射时候，定义一个变量记录下来
* 2. 判断记录的数量 超过 新节点的数量时，Array1 后面的所有节点都进行移除
*

代码实现

/* renderer.ts*/
{
  // 其他代码 
} else {
  // 乱序的部分， 中间的部分
  let s1 = i  // 老Array1 中间乱序的部分，开始遍历的位置 
  let s2 = i // 新 Array2 中间乱序的部分，开始遍历的位置 
  // 定义一个变量 ， 记录新Array2 中间乱序节点的数量
  const toBePatched = e2 - s2 + 1 // 3 - 2 + 1 -> 新Array2 乱序节点的数量 
  // 定义一个变量 记录新Array1 已经映射过的节点数量 当每次映射时候，定义一个变量记录下来
  let patched = 0 // Array1 已经映射过节点的数量
  // 2. 基于 新Array2 创建映射表， 存储Array2 中间乱序的节点部分
  const keyToNewIndexMap = new Map<string, number>()
  for (let i = s2; i <= e2; i++) {
    // 获取到当前节点 
    const nextChild = c2[i]
    // 添加到映射表中， key -> value , key 就是节点的key, value 为节点的索引值
    keyToNewIndexMap.set(nextChild.key, i)
  }
  // 定义一个遍历，保存 Array1 节点 在 Array2 中的位置 
  let newIndex
  // 3. 遍历 Array1 中间乱序的部分 
  for (let i = s1; i <= e1; i++) {
    // 获取到 Array1 当前的节点 
    const prevChild = c1[i]
    // 这里每次都需要去检查 patched 是否超过 toBePatched，如果超过，就不再进行循环了
    // patched 映射的次数 >= toBePatched 新节点的数量, 如果超过了，直接删除老节点
    if (patched >= toBePatched) {
      // 直接删除了，没必要执行下面的逻辑
      hostRemove(prevChild.el)
      continue
    }
    // 判断 Array1 当前节点 的属性是否具有key
    // 当前节点 没有key， 那么key就有两种 情况 null | undefined  
    if (prevChild.key !== null) {
      // 当有key 时，才会去判断是否在映射表中， 因为映射表基于 Array2 乱序节点 key 创建的
      // 根据在老Array 真正遍历的节点 key,  查找对应的映射表
      // 如果能获取到值 -> 新Array2中 一定存在该节点
      // 如果没有 -> 说明该节点在新Array2中不存在，需要删除
      newIndex = keyToNewIndexMap.get(prevChild.key)  // 返回索引值， 新节点所在位置 
      // 当 key 没有时 newIndex 为 undefined
    } else {
      // 如果没有 当前节点 没有设置 key 
      // 遍历 新Array2 中的节点，对比 Array1 中的节点, 判断是否存在
      // 如果不相同，删除老节点
      for (let j = s2; i <= e2; i++) {
        // 判断 新老节点是否相同 
        if (isSomeVNodeType(prevChild, c2[j])) {
          // 进行 newIndex 赋值 -> 新节点所在的位置
          newIndex = j
          // 查找到节点， 就没有必要遍历了
          break
        }
      }
    }
    // 4. 基于 newIndex索引，判断节点的状态 
    // 判断 newIndex 是否存在
    if (newIndex === undefined) {
      // 如果没有取到值 -> undefined，说明该节点在新Array2中不存在，需要删除
      // 删除老节点 ，也就是当前节点
      hostRemove(prevChild.el)
    } else {
      // 如果 newIndex 具有值 -> 新节点所在的位置
      // 调用patch() 进行更深度的对比 -> 进行判断 props | children 这些属性 
      patch(prevChild, c2[newIndex], container, parentComponent, null)
      // 这里表示已经映射完一个节点了，需要在这里赋值 patched + 1
      patched++
    }
  }
}

改完代码，根据DEMO，当Array1 遍历到 D 节点时， Array2创建的映射表，已经映射完了，所以 D 节点直接删除，不会执行深层的逻辑

6.5.2 中间对比 - 节点的移动

测试组件


// 中间节点 - 移动 - 节点存在于新的和老的里面，但是位置变了 
// a b (c d e) f g 
// a b (e c d) f g
// 最长递增子序列 [1, 2] -> c d
const prevChildren = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "E" }, "E"),
  h("p", { key: "F" }, "F"),
  h("p", { key: "G" }, "G"),
];
const nextChildren = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "E" }, "E"),  // E 节点移动
  h("p", { key: "C" }, "C"),
  h("p", { key: "D" }, "D"),
  h("p", { key: "F" }, "F"),
  h("p", { key: "G" }, "G"),
];
// 3. 中间节点移动节点的逻辑
/**
 * 1. 确定中间节点的不同，并且建立中间节点， 新Array 与 老Array 的映射关系
 * 2. 初始化映射表
 * 3. 赋值映射表
 * 4. 求最长递增子序列, 也就是新节点中不变的节点,一共有多少个
 * 5. 进行两个节点的对比
 */

代码实现

/* renderer.ts */
else {
  // 1. 需要遍历 Array1 和 Array2 中间乱序的部分
  // 创建指针 
  let s1 = i  // 老Array1 中间乱序的部分，开始遍历的位置 
  let s2 = i // 新 Array2 中间乱序的部分，开始遍历的位置 
  // 定义一个变量 ， 记录新Array2 中间乱序节点的数量
  const toBePatched = e2 - s2 + 1 // 3 - 2 + 1 -> 新Array2 乱序节点的数量 
  // 定义一个变量 记录新Array1 已经映射过的节点数量 当每次映射时候，定义一个变量记录下来
  let patched = 0 // Array1 已经映射过节点的数量
  let moved = false
  let maxNewIndexSofar = 0
  // 3. 中间节点移动节点的逻辑
  /**
       * 1. 确定中间节点的不同，并且建立中间节点， 新Array 与 老Array 的映射关系
       * 2. 初始化映射表 
       * 3. 赋值映射表 
       * 4. 求最长递增子序列, 也就是新节点中不变的节点,一共有多少个 
       * 5. 进行两个节点的对比
       */
  // 3.1. 建立映射表 新Array 与 老Array 的映射关系
  // 给定一个定长的数组， 因为性能更好，数组范围是，Array2 中间节点变化的数量 
  const newIndexToOldIndexMap = new Array(toBePatched)
  // 3.2. 初始化 映射表，  赋值为 i, i -> Array1 & Array2 的开始遍历位置
  //  表示没有建立映射关系 
  //  循环Array2, 初始化这个映射表 
  for (let i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
  // 其他代码 
  // 判断 newIndex 是否存在
  if (newIndex === undefined) {
    // 如果没有取到值 -> undefined，说明该节点在新Array2中不存在，需要删除
    // 删除老节点 ，也就是当前节点
    hostRemove(prevChild.el)
  } else {
    // 3.3 判断
    if (newIndex >= maxNewIndexSofar) {
      maxNewIndexSofar = newIndex
    } else {
      moved = true
    }
    // 这里赋值这个映射表 
    newIndexToOldIndexMap[newIndex - s2] = i + 1
    // 如果 newIndex 具有值 -> 新节点所在的位置
    // 调用patch() 进行更深度的对比 -> 进行判断 props | children 这些属性 
    patch(prevChild, c2[newIndex], container, parentComponent, null)
    // 这里表示已经映射完一个节点了，需要在这里赋值 patched + 1
    patched++
  }
  // 4. 获取最长递增子序列 
  const increasingNewIndexSequence = moved ? getSequence(newIndexToOldIndexMap) : []
  // 5. 进行节点的对比， 一个是新节点，一个是最长递增子序列 
  // 定义索引指针， 用于指向最长递增子序列
  let j = increasingNewIndexSequence.length - 1
  // 遍历 Array2 
  for (let i = toBePatched - 1; i >= 0; i--) {
    // 调用 insert() 方法 -> 基于锚点 
    const nextIndex = i + s2
    const nextChild = c2[nextIndex]
    // 锚点 
    const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : null
    // 创建节点逻辑
    if (newIndexToOldIndexMap[i] === 0) {
      patch(null, nextChild, container, parentComponent, anchor);
    } else if (moved) {  // 判断移动 
      if (j < 0 || i !== increasingNewIndexSequence[j]) {
        // 进行移动位置 
        // console.log("移动位置")
        hostInsert(nextChild.el, container, anchor)
      } else {
        // 不需要移动 
        j--
      }
    }
  }
}

求最长递增子序列

/* renderer.ts */
// 根据映射表，求最长递增子序列 
function getSequence(arr) {
  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;
}

E 节点的移动

6.5.3 中间对比 - 创建节点


// 3. 创建新的节点
// a,b,(c,e),f,g
// a,b,(e,c,d),f,g
// d 节点在老的节点中不存在，新的里面存在，所以需要创建
const prevChildren = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "C" }, "C"),
  h("p", { key: "E" }, "E"),
  h("p", { key: "F" }, "F"),
  h("p", { key: "G" }, "G"),
];
const nextChildren = [
  h("p", { key: "A" }, "A"),
  h("p", { key: "B" }, "B"),
  h("p", { key: "E" }, "E"),  // 移动 E 节点
  h("p", { key: "C" }, "C"),
  h("p", { key: "D" }, "D"), // 创建 D 节点
  h("p", { key: "F" }, "F"),
  h("p", { key: "G" }, "G"),
];

代码实现

/* renderer.ts */
// 4. 获取最长递增子序列 
const increasingNewIndexSequence = moved ? getSequence(newIndexToOldIndexMap) : []
// 5. 进行节点的对比， 一个是新节点，一个是最长递增子序列 
// 定义索引指针， 用于指向最长递增子序列
let j = increasingNewIndexSequence.length - 1
// 遍历 Array2 
for (let i = toBePatched - 1; i >= 0; i--) {
  // 调用 insert() 方法 -> 基于锚点 
  const nextIndex = i + s2
  const nextChild = c2[nextIndex]
  // 锚点 
  const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : null
  // 创建节点逻辑
  if (newIndexToOldIndexMap[i] === 0) {
    patch(null, nextChild, container, parentComponent, anchor);
  } else if (moved) {  // 判断移动 
    if (j < 0 || i !== increasingNewIndexSequence[j]) {
      // 进行移动位置 
      // console.log("移动位置")
      hostInsert(nextChild.el, container, anchor)
    } else {
      // 不需要移动 
      j--
    }
  }
}

mini-vue 实践笔记

六、实现Element children 更新 - diff算法

Array -> Array的几种情况

6.1 左侧对比

happy patch

实现左侧对比的逻辑

6.2 右侧对比

happy patch

实现右侧对比

6.3 diff算法 - 创建节点

左侧一样，新的Array比老的Array长 - 创建新节点

右侧一样，新的Array比老的长Array - 创建新节点

修复 bug

6.4 diff 算法 - 删除节点

左侧一样，老的Array的比新的Array长 - 删除老节点

右侧一样，老的Array的比新的Array长 - 删除老节点

6.5 diff 算法 - 中间对比

6.5.1 中间对比 - 删除老节点

优化删除的逻辑

6.5.2 中间对比 - 节点的移动

6.5.3 中间对比 - 创建节点

六、实现Element children 更新 - diff算法

Array -> Array的几种情况

6.1 左侧对比

happy patch

实现左侧对比的逻辑

6.2 右侧对比

happy patch

实现右侧对比

6.3 diff算法 - 创建节点

左侧一样，新的Array比老的Array长 - 创建新节点

右侧一样， 新的Array比老的长Array - 创建新节点

修复 bug

6.4 diff 算法 - 删除节点

左侧一样，老的Array的比新的Array长 - 删除老节点

右侧一样，老的Array的比新的Array长 - 删除老节点

6.5 diff 算法 - 中间对比

6.5.1 中间对比 - 删除老节点

优化删除的逻辑

6.5.2 中间对比 - 节点的移动

6.5.3 中间对比 - 创建节点

右侧一样，新的Array比老的长Array - 创建新节点