likes
comments
collection
share

小狐狸学mini-vue(四、diff 算法)

作者站长头像
站长
· 阅读数 18

仓库地址

文章导航

30、更新elelemt 的props

弄清楚元素的属性可能发生那些变化?

1.修改、删除、和新增。

代码实现 runtime-dom/index.ts

// 添加新老属性的值
function patchProp(el, key, prevVal, nextVal) {
  const isOn = (key: string) => /^on[A-Z]/.test(key);
  if (isOn(key)) {
    const event = key.slice(2).toLowerCase();
    el.addEventListener(event, nextVal);
  } else {
    // 删除属性
    if (nextVal === undefined || nextVal === null) {
      el.removeAttribute(key);
    } else {
      // 修改和添加属性
      el.setAttribute(key, nextVal);
    }
  }
}

renderer.ts

  function patchElement(n1, n2, container) {
    console.log("patchElement");
    console.log("n1", n1);
    console.log("n2", n2);

    let oldProps = n1.props || {};
    let newProps = n2.props || {};

    // 复用老元素 在同一个 DOM 上面打补丁
    let el = (n2.el = n1.el);
    // 在对比元素的时候对比 属性
    patchProps(el, oldProps, newProps);
  }

  function patchProps(el, oldProps, newProps) {
    // 遍历新的属性
    for (let key in newProps) {
      const prevProp = oldProps[key];
      const nextProp = newProps[key];
      // 如果两者不相等就更新 新增或者修改
      if (prevProp !== nextProp) {
        hostPatchProp(el, key, prevProp, nextProp);
      }
    }
    // 遍历老的节点
    for (let key in oldProps) {
      const prevProp = oldProps[key];
      if (!(key in newProps)) {
        // 新的中有,老的中没有则执行删除操作。
        hostPatchProp(el, key, prevProp, null);
      }
    }
  }
  
  function mountElement(vnode: any, container: any, parentComponent) {
    .....
    for (let key in props) {
      let val = props[key];
      hostPatchProp(el, key, null, val);
    }
    .....
  }

测试代码

小狐狸学mini-vue(四、diff 算法)

31、更新element的children

每一种老儿子类型,都可能有两种新类型对应。

老儿子新儿子操作方式
文本文本(更新文本即可)
文本数组(删除老儿子,挂载新儿子)
数组文本(清空老儿子,设置新文本)
数组数组(diff算法)

在这里再强调一下,更新的时候 patch的时候新老节点是从哪里获取到的。

从组件实例上获取老的subTeee新的是数据变化之后再重新执行组件的render函数,拿到最新的虚拟节点树的。

 console.log("更新");
const { proxy } = instance;
// 最新的 subTree
const subTree = instance.render.call(proxy);
// 获取老的 subTree
const prevSubTree = instance.subTree;
// 更新老的 subTree
instance.subTree = subTree;
console.log("prevSubTree", prevSubTree);
console.log("subTree", subTree);
patch(prevSubTree, subTree, container, instance);

代码实现

function patchElement(n1, n2, container, parentComponent) {
    console.log("patchElement");
    console.log("n1", n1);
    console.log("n2", n2);

    let oldProps = n1.props || {};
    let newProps = n2.props || {};

    // 复用老元素 在同一个 DOM 上面打补丁
    let el = (n2.el = n1.el);
    // 对比孩子
    patchChildren(n1, n2, el, parentComponent);
    .....
  }
  function patchChildren(n1, n2, el, parentComponent) {
    // 先拿到新节点的 vnode 和 shapeFlag
    const prevShapeFlag = n1.shapeFlag;
    const c1 = n1.children;
    const { shapeFlag } = n2;
    const c2 = n2.children;
    // 新节点是 text
    if (shapeFlag & ShapeFlags.TEXT_CHILDREN) {
      // 老节点就只能有两种情况 text 或者 array
      // 老节点是数组
      if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
        // 卸载老儿子,并更新文本
        unmountChildren(n1.children);
      }
      // 老节点是文本
      if (c1 !== c2) {
        // 如果不行等则直接更新
        hostSetElementText(el, c2);
      }
    }
    // 新节点是数组
    else {
      // 老节点是 text
      if (prevShapeFlag & ShapeFlags.TEXT_CHILDREN) {
        // 卸载老文本,挂载新节点
        hostSetElementText(el, "");
        // 挂载新儿子节点
        mountChildren(c2, el, parentComponent);
      } else {
        console.log("diff 算法");
      }
    }
  }

  /**
   * 删除一组儿子
   * @param children
   */
  function unmountChildren(children) {
    for (let i = 0; i < children.length; i++) {
      const el = children[i].el;
      hostRemove(el);
    }
  }

测试代码

TextToText.js

import { h, ref } from "../../lib/vue3-mini-vue.esm.js";

const prevChildren = "oldChild";
const nextChildren = "newChild";

export default {
  name: "TextToText",
  setup() {
    const isChange = ref(false);
    window.isChange = isChange;

    return {
      isChange,
    };
  },
  render() {
    return this.isChange
      ? h("div", {}, nextChildren)
      : h("div", {}, prevChildren);
  },
};

TextToArray.js

import { h, ref } from "../../lib/vue3-mini-vue.esm.js";

const prevChildren = "oldChild";
const nextChildren = [h("div", {}, "1"), h("div", {}, "2"), h("div", {}, "3")];

export default {
  name: "TextToArray",
  setup() {
    const isChange = ref(false);
    window.isChange = isChange;

    return {
      isChange,
    };
  },
  render() {
    return this.isChange
      ? h("div", {}, nextChildren)
      : h("div", {}, prevChildren);
  },
};

ArrayToText.js

import { h, ref } from "../../lib/vue3-mini-vue.esm.js";

const prevChildren = [h("div", {}, "1"), h("div", {}, "2"), h("div", {}, "3")];
const nextChildren = "oldChild";

export default {
  name: "ArrayToText",
  setup() {
    const isChange = ref(false);
    window.isChange = isChange;

    return {
      isChange,
    };
  },
  render() {
    return this.isChange
      ? h("div", {}, nextChildren)
      : h("div", {}, prevChildren);
  },
};

老节点是text 新节点是text情况测试

小狐狸学mini-vue(四、diff 算法)

老节点是text 新节点是array情况测试

小狐狸学mini-vue(四、diff 算法) 老节点是array新节点是text测试

小狐狸学mini-vue(四、diff 算法)

32、更新element的children 双端对比算法

DIFF 算法的目的就是找到两组子节点中有差异的地方,然后进行打补丁:创建新的、删除老的、还有移动元素位置。

找到中间的差异部分:差异部分可能包含三种情况,

  1. 创建新的、
  2. 删除老的、
  3. 移动元素(元素存在于新的和老的里面,但是位置变了)

3、新的比老的多

3.1、后面插入新元素

i <= e2, [i , e2]之间的元素都是要新插入的元素。

小狐狸学mini-vue(四、diff 算法)

小狐狸学mini-vue(四、diff 算法)

3.2、前面插入新元素

这个和之前向后面插入的时候不太一样,他插入需要一个参考点,要插入的元素区间仍然是 [i , e2] 的这个区间的元素。 小狐狸学mini-vue(四、diff 算法)

用 e2 当前的位置nextPos = l2 + 1看看是否大于 l2 (新孩子的长度),如果大于则表示在后面插入,如果小于 l2,则就用 nextPos位置的元素作为往前面插入元素的锚点,依次插入新节点即可。

小狐狸学mini-vue(四、diff 算法)

小狐狸学mini-vue(四、diff 算法)

4、老的比新的多

4.1、删除后面多余的元素

从前面开始对比,后面的多了,删除后面的元素

要删除的区间就是 [i, e1]之间的元素。 小狐狸学mini-vue(四、diff 算法)

小狐狸学mini-vue(四、diff 算法)

4.2、删除前面多余的元素

从后面开始对比,前面多了,删除前面的元素

经过观察发现,要删除的元素区间还是 [i, e1]之间的元素。 小狐狸学mini-vue(四、diff 算法)

小狐狸学mini-vue(四、diff 算法)

5、对比中间的部分

5.1、删除老的

(在老的里面存在,在新的里面不存在)

  • 遍历老节点,看老节点在新节点中是否还存在,如果不存在,则删除掉,如果存在则进行 patch 进行更详细的比对。
const prevChildren = [
  h("div", { key: "A" }, "A"),
  h("div", { key: "B" }, "B"),
  h("div", { key: "C" }, "C"),
  h("div", { key: "D" }, "D"),
  h("div", { key: "F" }, "F"),
  h("div", { key: "G" }, "G"),
];
const nextChildren = [
  h("div", { key: "A" }, "A"),
  h("div", { key: "B" }, "B"),
  h("div", { key: "E" }, "E"), // 新增的先不管
  h("div", { key: "C" }, "C"),
  h("div", { key: "F" }, "F"),
  h("div", { key: "G" }, "G"),
];

我们用图来画一下,大概是下面这个样子。

小狐狸学mini-vue(四、diff 算法) 当我们确定了中间差异的部分,然后在找出要删除的老节点,就可以通过下面的两个步骤来完成。

  1. 先用个新节点的keyindex创建一个Map,遍历老的元素,看看这个Map中是否存在,如果不存在,则表示这个老节点需要删除。
  2. 如果元素没有key则通过再次遍历新节点的方式,判断老节点是否在新节点中存在。 小狐狸学mini-vue(四、diff 算法) 这部分的代码实现如下

renderer.ts

  function patchKeyedChildren(c1, c2, container, parentComponent, anchor) {
    ......
    // 从左侧开始进行对比
    while (i <= e1 && i <= e2) {
      ......
    }
    console.log(`前前对比结束`, i, e1, e2);
    while (i <= e1 && i <= e2) {
     .....
    }
    console.log(`后后对比结束`, i, e1, e2);
    if (i > e1) {
      // 新的比老的多
      // 这个区间代表了多出来的元素
     .......
      }
    } else if (i > e2) {
      // 老的比新的多
      // 要删除的区间就是 [i, e1] 之间的元素
     .......
    } else {
      console.log("中间对比");
      let s1 = i;
      let s2 = i;

      // 新元素中间的个数

      // 用新元素的 key 和下标构建一个 Map 对象
      const keyToNewIndexMap = new Map();

      // 遍历新元素中间剩余的
      for (let i = s2; i <= e1; i++) {
        const nextChild = c2[i];
        keyToNewIndexMap.set(nextChild.key, i);
      }

      // 遍历老的元素,看老的元素是否在新的元素中出现。
      for (let i = s1; i <= e1; i++) {
        const prevChild = c1[i];

        let newIndex;
        // 如果老的 vnode 里面有 key,则去新节点构建的 map 中去查找
        // null 和 undefined
        if (prevChild.key != null) {
          newIndex = keyToNewIndexMap.get(prevChild.key);
        } else {
          // 如果没有可以,则进行双重循环对比 n²
          // 遍历新的节点
          for (let j = s2; j <= e2; j++) {
            if (isSameVNodeType(prevChild, e2[j])) {
              newIndex = j;
              break;
            }
          }
        }
        // 如果老节点在新节点中不存在,则将其移除掉
        if (newIndex === undefined) {
          hostRemove(prevChild.el);
        } else {
          patch(prevChild, c2[newIndex], container, parentComponent, null);
        }
      }
    }
  }

每个节点分有 key 和没有 key 的情况。

5.2、老的比新的多

优化。

如果已经patch过的元素个数比新的元素多,那么多出来的老节点就直接可以被删除掉。

举例子

const prevChildren = [
  h("div", { key: "A" }, "A"),
  h("div", { key: "B" }, "B"),
  h("div", { key: "C", id: "c-prev" }, "C"),
  h("div", { key: "E" }, "E"),
  h("div", { key: "D" }, "D"),
  h("div", { key: "F" }, "F"),
  h("div", { key: "G" }, "G"),
];
const nextChildren = [
  h("div", { key: "A" }, "A"),
  h("div", { key: "B" }, "B"),
  h("div", { key: "E" }, "E"),
  h("div", { key: "C", id: "c-next" }, "C"),
  h("div", { key: "F" }, "F"),
  h("div", { key: "G" }, "G"),
];

代码实现

else {
  console.log("中间对比");
  let s1 = i;
  let s2 = i;

  // 将要对比的中间差异元素的个数
  const toBePatched = e2 - s2 + 1;

  // 新老节点相同的,已经深度patch过的元素
  let patched = 0;
  .......
  // 遍历老的元素,看老的元素是否在新的元素中出现。
  for (let i = s1; i <= e1; i++) {
    const prevChild = c1[i];
    // 如果对比过的元素个数大于新的中间插入元素的个数,则剩下的都要删除掉。
    if (patched >= toBePatched) {
      // 移除老的元素
      hostRemove(prevChild.el);
      continue;
    }

    ...........
    // 如果老节点在新节点中不存在,则将其移除掉
    if (newIndex === undefined) {
      .......
    } else {
      patch(prevChild, c2[newIndex], container, parentComponent, null);
      patched++;
    }
  }
}

在补张,理解一下吧。

小狐狸学mini-vue(四、diff 算法)

学到这里,来说一说,在我们写代码的时候,key的作用是什么?

用来判断新老vnode中节点是否是同一个。

6、位置发生变化,需要移动元素

当元素在新的里面存在,同时也在老的里面存在的时候,这个时候就要进行元素位置的移动了。

新元素的索引和最长递增子序列索引相匹配的时候,就不需要移动节点。

最后来画一张图理解一下吧。

小狐狸学mini-vue(四、diff 算法)

测试代码

// 中间部分, 老的比新的多,那么多出来的直接就可以删除掉 ,(已经patch过的元素大于等于中间新元素的个数)优化删除逻辑
// const prevChildren = [
//   h("div", { key: "A" }, "A"),
//   h("div", { key: "B" }, "B"),
//   h("div", { key: "C", id: "c-prev" }, "C"),
//   h("div", { key: "E" }, "E"),
//   h("div", { key: "D" }, "D"),
//   h("div", { key: "F" }, "F"),
//   h("div", { key: "G" }, "G"),
// ];
// const nextChildren = [
//   h("div", { key: "A" }, "A"),
//   h("div", { key: "B" }, "B"),
//   h("div", { key: "E" }, "E"), // 新增的先不管
//   h("div", { key: "C", id: "c-next" }, "C"),
//   h("div", { key: "F" }, "F"),
//   h("div", { key: "G" }, "G"),
// ];

// 2 移动(节点存在于新的和老的里面,但是位置变了)
// const prevChildren = [
//   h("div", { key: "A" }, "A"),
//   h("div", { key: "B" }, "B"),
//   h("div", { key: "C" }, "C"),
//   h("div", { key: "D" }, "D"),
//   h("div", { key: "E" }, "E"),
//   h("div", { key: "F" }, "F"),
//   h("div", { key: "G" }, "G"),
// ];
// const nextChildren = [
//   h("div", { key: "A" }, "A"),
//   h("div", { key: "B" }, "B"),
//   h("div", { key: "E" }, "E"),
//   h("div", { key: "C" }, "C"),
//   h("div", { key: "D" }, "D"),
//   h("div", { key: "F" }, "F"),
//   h("div", { key: "G" }, "G"),
// ];

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

// 综合例子
// a,b,(c,d,e,z),f,g
// a,b,(d,c,y,e),f,g
// 新元素在老元素中索引的位置 [4,3,0,5]   [newIndex - s2] =  i(新节点在老节点中的位置)
// ce 最长递增序列
// y 新增
// 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: "Z" }, "Z"),

  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: "D" }, "D"),
  h("p", { key: "C" }, "C"),
  h("p", { key: "Y" }, "Y"),
  h("p", { key: "E" }, "E"),

  h("p", { key: "F" }, "F"),
  h("p", { key: "G" }, "G"),
];
export default {
  name: "ArrayToArray",
  setup() {
    const isChange = ref(false);
    window.isChange = isChange;

    return {
      isChange,
    };
  },
  render() {
    return this.isChange
      ? h("div", {}, nextChildren)
      : h("div", {}, prevChildren);
  },
};

renderer.js

  function patchKeyedChildren(c1, c2, container, parentComponent, anchor) {
    ......
    if (i > e1) {
      // 新的比老的多
     .....
    } else if (i > e2) {
     ......
    } else {
      console.log("中间对比");
      let s1 = i;
      let s2 = i;

      // 将要对比的中间差异元素的个数
      const toBePatched = e2 - s2 + 1;

      // 新老节点相同的,已经深度patch过的元素
      let patched = 0;

      // 用新元素的 key 和下标构建一个 Map 对象
      const keyToNewIndexMap = new Map();
      // 用一个 map 来收集 差异节点中新节点在老节点中的位置
      const newIndexToOldIndexMap = new Array(toBePatched); // 初始化长度等于新元素
      // 记录 元素是否移动位置
      let moved = false;
      let maxNewIndexSoFar = 0;
      // 先给每一个初始化为 0
      for (let i = 0; i < toBePatched; i++) {
        newIndexToOldIndexMap[i] = 0;
      }

      // 遍历新元素中间剩余的
      for (let i = s2; i <= e2; i++) {
        const nextChild = c2[i];
        keyToNewIndexMap.set(nextChild.key, i);
      }

      // 遍历老的元素,看老的元素是否在新的元素中出现。
      for (let i = s1; i <= e1; i++) {
        const prevChild = c1[i];

        if (patched >= toBePatched) {
          // 移除老的元素
          hostRemove(prevChild.el);
          continue;
        }

        let newIndex;
        // 如果老的 vnode 里面有 key,则去新节点构建的 map 中去查找
        // null 和 undefined
        if (prevChild.key != null) {
          newIndex = keyToNewIndexMap.get(prevChild.key);
        } else {
          // 如果没有可以,则进行双重循环对比 n²
          // 遍历新的节点
          for (let j = s2; j <= e2; j++) {
            if (isSameVNodeType(prevChild, e2[j])) {
              newIndex = j;
              break;
            }
          }
        }
        // 如果老节点在新节点中不存在,则将其移除掉
        if (newIndex === undefined) {
          hostRemove(prevChild.el);
        } else {
          // 老节点中存在,新节点中也存在
          // 如果 新节点一直大于迄今为止最大的索引,则说明没有元素位置发生了变化
          if (newIndex >= maxNewIndexSoFar) {
            // 更新当前最大的索引值
            maxNewIndexSoFar = newIndex;
          } else {
            // 如果一旦有小于最大的索引,则说明元素位置发生了变化
            moved = true;
          }
          newIndexToOldIndexMap[newIndex - s2] = i + 1; // i 代表 新节点在老节点中的位置。
          patch(prevChild, c2[newIndex], container, parentComponent, null);
          patched++;
        }
      }
      // 老元素对比完成之后,看看是否有要移动的元素,如果有,则需要用新元素在老元素中的位置求出,最大递增子序列
      const increasingNewIndexSequence = moved
        ? getSequence(newIndexToOldIndexMap)
        : [];
      // 取出最长递增子序列的最后一位
      let j = increasingNewIndexSequence.length - 1;

      // 倒序遍历中间的差异元素
      for (let i = toBePatched - 1; i >= 0; i--) {
        // 当前遍历元素在新节点中的位置索引
        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]) {
            // 需要移动当前新的节点
            hostInsert(nextChild.el, container, anchor);
          } else {
            // 不需要移动元素
            j--;
          }
        }
      }
    }
  }
  
  
     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;
}

转载自:https://juejin.cn/post/7274084216286986276
评论
请登录