简单Diff算法

2024-01-02 08:42:13

简单Diff算法

渲染器的核心

Diff算法

解决的问题

比较新旧虚拟节点的子节点,实现最小化更新。

虚拟节点key属性的作用

就像虚拟节点的“身份证号”,在更新时,渲染器会通过key属性找到可复用的节点,然后尽可能地通过DOM移动操作来完成更新,避免过多地对 DOM 元素进行销毁和重建。key和type的属性值均都相同,则两个节点就是相同的,即可实现进行DOM的复用。

简单Diff算法地核心逻辑(如何寻找需要移动的节点)

拿新一组子节点中的节点去旧的一组子节点中去寻找可复用的节点。如果找到了,则记录该节点的位置索引。我们把这个索引称为最大索引。在整个更新过程中,如果一个节点的索引小于最大索引,则说明该节点需要移动。

节点的移动

使用的是insert方法,找到锚点元素进行插入操作,其中insert方法对于浏览器来说依赖于原生的insertBefore函数。

在这里插入图片描述

源码展示
function patchChildren(n1, n2, container) {
  if (typeof n2.children === 'string') {
    // 省略部分代码
  } else if (Array.isArray(n2.children)) {
    const oldChildren = n1.children;
    const newChildren = n2.children
    // 用来存储寻找过程中遇到的最大索引值
    let lastIndex = 0;
    for (let i = 0; i < newChildren.length; i++) {
      const newVNode = newChildren[i];
      for (let j = 0; j < oldChildren.length; j++) {
        const oldVNode = oldChildren[j];
        if (newVNode.key === oldVNode.key) {
          // 进行打补丁
          patch(oldVNode, newVNode, container);
          if (j < lastIndex) {
            // 如果当前找到的节点在旧节点中的索引值小于最大索引值lastIndex,
            // 说明该节点对应的真实的DOM节点需要进行移
            // 先获取 newVNode 的前一个vnode,即 preVNode
            const preVNode = newChildren[i - 1]
            // 如果 prevVNode 不存在,则说明当前的 newVNode 是第一个节点,它不需要移动
            if (prevVNode) {
              // 由于我们需要将 newVNode 对应的真实DOM移动到 prevVNode 所对应的真实DOM后面,
              // 所以我们需要获取到 prevVNode 所对应的真实DOM的下一个兄弟节点,以此作为锚点
              
              const anchor = prevVNode.el.nextSibling();
              // 调用insert方法将 newVNode 对应的真实DOM插入到锚点元素的前面
              // 也就是 prevVNode 对应的真实DOM的后
              insert(newVNode.el, prevVNode.el, anchor);
            }
          } else {
            // 如果当前找到的节点在旧节点中的索引值大于或等于最大索引值lastIndex,
            // 则更新最大索引lastIndex的值
            lastIndex = j;
          }
          break;
        }
      }
    }
  }
}

上面代码中,如果j < lastIndex成立,则说明当前newVNode所对应的真实DOM节点需要移动。我们需要先获取当前 newVNode 节点的前一个虚拟节点,即newChildren[i - 1],然后使用insert函数完成节点的移动,其中insert 函数依赖浏览器原生的insertBefore函数。如下:

const renderer = createRenderer({
  // 省略部分代码
  insert(el, parent, anchor = null) {
    // insertBefore 需要锚点元素anchor
    parent.insertBefore(el, anchor);
  }
  // 省略部分代码
});
添加新元素

在新一组的子节点中对应的key没有在旧一组子节点中存在的节点,即为新节点。

在这里插入图片描述

如上图所示,p-4节点是一个需要新增的节点。在遍历的过程中能够发现p-4节点的key值在旧子节点中没有对应找到(视为新增节点),需要将p-4节点对应的真实DOM挂载在p-1节点对应的真实DOM节点的后面。

源码展示

function patchChildren(n1, n2, container) {
  if (typeof n2.children === 'string') {
    // 省略部分代码
  } else if (Array.isArray(n2.children)) {
    const oldChildren = n1.children;
    const newChildren = n2.children
    // 用来存储寻找过程中遇到的最大索引值
    let lastIndex = 0;
    for (let i = 0; i < newChildren.length; i++) {
      const newVNode = newChildren[i]
      // 在第一层循环中定义变量find,代表是否在旧的一组子节点中找到可以复用的节点
      // 初始值为false,代表没有找到
      let find = false;
      
      for (let j = 0; j < oldChildren.length; j++) {
        const oldVNode = oldChildren[j];
        if (newVNode.key === oldVNode.key) {
          
          // 找到可复用的节点,将find置为true
          find = true;
          
          // 进行打补丁
          patch(oldVNode, newVNode, container);
          if (j < lastIndex) {
            // 如果当前找到的节点在旧节点中的索引值小于最大索引值lastIndex,
            // 说明该节点对应的真实的DOM节点需要进行移
            // 先获取 newVNode 的前一个vnode,即 preVNode
            const preVNode = newChildren[i - 1]
            // 如果 prevVNode 不存在,则说明当前的 newVNode 是第一个节点,它不需要移动
            if (prevVNode) {
              // 由于我们需要将 newVNode 对应的真实DOM移动到 prevVNode 所对应的真实DOM后面,
              // 所以我们需要获取到 prevVNode 所对应的真实DOM的下一个兄弟节点,以此作为锚点
              
              const anchor = prevVNode.el.nextSibling();
              // 调用insert方法将 newVNode 对应的真实DOM插入到锚点元素的前面
              // 也就是 prevVNode 对应的真实DOM的后
              insert(newVNode.el, prevVNode.el, anchor);
            }
          } else {
            // 如果当前找到的节点在旧节点中的索引值大于或等于最大索引值lastIndex,
            // 则更新最大索引lastIndex的值
            lastIndex = j;
          }
          break;
        }
      }
      
      // 若代码运行至此,find仍为false
      // 说明当前 newVNode 没有在旧一组子节点找到可复用的节点
      // 即 newVNode 为新增节点,需要挂载
      if (!find) {
        // 为了将新增节点挂载到正确的位置,我们需要找到锚点元素
        // 获取 newVNode 的前一个 vnode 节点
        const prevVNode = newChildren[i - 1];
        let anchor = null;
        if (prevVNode) {
          // 如果有前一个 vnode 节点,则使用它的下一个兄弟节点作为锚点元素
          anchor = prevVNode.el.nextSibling;
        } else {
          // 如果没有前一个 vnode 节点,则说明即将挂载的节点是第一个子节点
          // 这时我们使用容器元素的 firstChild 作为锚点
          anchor = container.firstChild;
        }
        // 挂载 newVNode
         patch(null, newVNode, container, anchor);
      }
    }
  }
}

上面的代码,首先我们在外层循环中定义了find变量,它表示新一组子节点是否在旧一组子节点中找到可复用的节点。变量find初始值为false,一旦找到可复用的子节点就将find置为true。如果内层循环结束后,find值仍然为false,说明当前 newVNode 是一个新增节点,需要挂载。为了找到此节点被挂载的位置,我们要获取到锚点元素:找到 newVNode 前一个虚拟节点,即 prevNode。如果存在 prevNode 存在,那么我们就取 prevNode 节点的下一个兄弟节点对应的真实DOM元素作为锚点,进行挂载;如果不存在,则说明当前需要挂载的 newVNode 节点是第一个子节点,此时应该使用容器元素的container.firstChild作为锚点。最后将锚点 anchor 作为patch函数的第四个参数,调用 patch 函数进行挂载。

patch函数如下:

// patch 函数需要接收四个参数
// n1: 旧vnode
// n2: 新vnode
// container: 容器
// anchor: 锚点元素
function patch(n1, n2, container, anchor) {
  // 省略部分代码
  if (typeof type === 'string') {
    if (!n1) {
      // 挂载时将锚点元素作为第三个参数传递给 mountElement 函数
      mountElement(n2, container, anchor);
    } else {
      patchElement(n1, n2);
    }
  } else if (typeof type === Text) {
    // 省略部分代码
  } else if (typeof type === Fragment) {
    // 省略部分代码
  }
}

// mountElement 函数
function mountElement(vnode, container, anchor) {
  // 省略部分代码
  // 在插入节点时,将锚点元素透传给 insert 函数
  insert(el, container, anchor);
}

移除不存在的元素

在这里插入图片描述

如上图所示,节点p-2是需要被删除的元素。

源码展示

    function patchChildren(n1, n2, container) {
      if (typeof n2.children === 'string') {
        // 省略部分代码
      } else if (Array.isArray(n2.children)) {
        const oldChildren = n1.children;
        const newChildren = n2.children;

        // 用来存储寻找过程中遇到的最大索引值
        let lastIndex = 0;
        for (let i = 0; i < newChildren.length; i++) {
          // 省略部分代码
        }

        // 上一步的更新操作完成后,遍历旧的一组子节点
        for (let i = 0; i < oldChildren.length; i++) {
          const oldVNode = oldChildren[i];
          // 拿旧子节点 oldVNode 去新的一组子节点中寻找具有相同 key 值的节点
          const has = newChildren.find(ele => ele.key === oldVNode.key);
          if (!has) {
            // 如果没有找到具有相同 key 的节点,则说明需要删除该节点
            // 调用 unmount 函数将其卸载
            unmount(oldVNode);
          } else {
            // 省略部分代码
          }
        }
      }
    }

更新结束后,增加删除额外节点的逻辑来删除遗留节点。当基本的更新结束后,需要遍历旧的一组子节点,然后去新的一组子节点中去寻找具有相同 key 值的节点。如果找不到,则说明需要删除该节点(调用unmount函数将其卸载)。

文章来源:https://blog.csdn.net/dfc_dfc/article/details/135325649
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。