[记录]我的Diff算法学习路径

Catalog

1. Vue.js
   1.1 patch 流程
   1.2 updateChildren 大概步骤
   1.3 updateChildren 代码实现
   1.4 两端比对 DEMO
2. React.js
   2.1 updateChildren 大概步骤
   2.2 updateChildren 代码实现
   2.3 节点移动、新增 、移除 DEMO
3. Reference

Vue.js Diff 算法

patch 流程

- oldVNode 判断 是否存在
  - oldVNode 存在
    - VNode 判断 是否存在
      - VNode 存在
        - patch
          - sameVnode 判断 key && tag && isComment && isDef(a.data) && sameInputType(a, b) 基本属性是否相同
            - sameVnode 相同
              - diff
                - VNode 判断 是否是文本节点
                  - 是，若 oldVNode.text !== VNode.text 则直接进行文本节点替换
                  - 否，进入子节点 diff
                    - oldCh 不存在，cn 存在，清空 oldVNode 的文本节点，同时调用 addVnodes 方法将 cn 添加到 elm 真实的 dom 节点中
                    - oldCh 节点存在，cn 不存在，则删除 elm 真实节点下的 oldCn 子节点
                    - oldCh 存在，cn 存在，调用 updateChildren 对子节点进行 diff
                    - oldVNode 有文本节点，vnode 没有，那么就清空这个文本节点
            - sameVnode 不相同
              - 删除老的 dom 节点，生成新的 dom
      - VNode 不存在
        - 移除 DOM
  - oldVNode 不存在
    - 挂载 DOM

updateChildren 大概步骤

1. 建立两组首尾索引和节点变量

2. 当满足 oldStartIdx <= oldEndIdx 并且 newStartIdx <= newEndIdx 条件时进入循环

   1. 双端比较 => 循环中先进行比较找出 key 相同的新旧节点，根据四种情况判断是否移动 DOM 和增减首尾索引变量以及 patch

   2. 有 key 时 => 当双端匹配没有找到 key 相同的节点，通过当前 newStartVNode 的 key 在 nextChildren 中寻找 key 相同的 VNode

      1. key 相同的 VNode 存在时，对当前节点进行移动 DOM、patch 并将旧 children 中该位置的节点设为 undefined，将 newStartIdx 下移一位
      2. key 相同的 VNode 不存在，则当前“第一个”节点为新节点，将其挂载到 oldStartVNode 之前，将 newStartIdx 下移一位

3. 挂载全新的节点

   1. 当 oldEndIdx < oldStartIdx, 添加新节点

4. 移除不存在的节点

   1. 当 newEndIdx < newStartIdx, 移除不存在的元素

updateChildren 代码实现

// 建立两组首尾索引
let oldStartIdx = 0;
let oldEndIdx = prevChildren.length - 1;
let newStartIdx = 0;
let newEndIdx = nextChildren.length - 1;
// 索引对应的VNode
let oldStartVNode = prevChildren[oldStartIdx];
let oldEndVNode = prevChildren[oldEndIdx];
let newStartVNode = nextChildren[newStartIdx];
let newEndVNode = nextChildren[newEndIdx];
// 进行执行双端比较-简略流程版
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (oldStartVNode.key === newStartVNode.key) {
    // 步骤一：oldStartVNode 和 newStartVNode 比对
    ...
  } else if (oldEndVNode.key === newEndVNode.key) {
    // 步骤二：oldEndVNode 和 newEndVNode 比对
    ...
  } else if (oldStartVNode.key === newEndVNode.key) {
    // 步骤三：oldStartVNode 和 newEndVNode 比对
    ...
  } else if (oldEndVNode.key === newStartVNode.key) {
    // 步骤四：oldEndVNode 和 newStartVNode 比对
    ...
  }else {
    // 当双端比对没有匹配节点时，遍历旧 children，试图寻找与 newStartVNode 拥有相同 key 值的元素
  }
}
// 进行执行双端比较-详细流程版
// 处理捕获，移动DOM，增减序号
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (!oldStartVNode) {
    // 当旧VNode已被diff移到别的位置时，旧VNode节点为undefined需要跳过当前索引
    oldStartVNode = prevChildren[++oldStartIdx]
  } else if (!oldEndVNode) {
    // 当旧VNode已被diff移到别的位置时，旧VNode节点为undefined需要跳过当前索引
    oldEndVNode = prevChildren[--oldEndIdx]
  } else if (oldStartVNode.key === newStartVNode.key) {
    // 步骤一：oldStartVNode 和 newStartVNode 比对
    // 调用 patch 函数更新
    patch(oldStartVNode, newStartVNode, container)
    // 更新索引，指向下一个位置
    oldStartVNode = prevChildren[++oldStartIdx]
    newStartVNode = nextChildren[++newStartIdx]
  } else if (oldEndVNode.key === newEndVNode.key) {
    // 步骤二：oldEndVNode 和 newEndVNode 比对
    // 调用 patch 函数更新
    patch(oldEndVNode, newEndVNode, container)
    // 更新索引，指向下一个位置
    oldEndVNode = prevChildren[--oldEndIdx]
    newEndVNode = nextChildren[--newEndIdx]
  } else if (oldStartVNode.key === newEndVNode.key) {
    // 步骤三：oldStartVNode 和 newEndVNode 比对
    // 调用 patch 函数更新
    patch(oldStartVNode, newEndVNode, container)
    // 将 oldStartVNode.el 移动到 oldEndVNode.el 的后面，也就是 oldEndVNode.el.nextSibling 的前面
    container.insertBefore(
      oldStartVNode.el,
      oldEndVNode.el.nextSibling
    )
    // 更新索引，指向下一个位置
    oldStartVNode = prevChildren[++oldStartIdx]
    newEndVNode = nextChildren[--newEndIdx]
  } else if (oldEndVNode.key === newStartVNode.key) {
    // 步骤四：oldEndVNode 和 newStartVNode 比对
    // 先调用 patch 函数完成更新
    patch(oldEndVNode, newStartVNode, container)
    // 更新完成后，将容器中最后一个子节点移动到最前面，使其成为第一个子节点
    container.insertBefore(oldEndVNode.el, oldStartVNode.el)
    // 更新索引，指向下一个位置
    oldEndVNode = prevChildren[--oldEndIdx]
    newStartVNode = nextChildren[++newStartIdx]
  } else {
    // 当双端比对没有匹配节点时，遍历旧 children，试图寻找与 newStartVNode 拥有相同 key 值的元素
    const idxInOld = prevChildren.findIndex(
      node => node.key === newStartVNode.key
    )
    if (idxInOld >= 0) {
      // vnodeToMove 就是在旧 children 中找到的节点，该节点所对应的真实 DOM 应该被移动到最前面
      const vnodeToMove = prevChildren[idxInOld]
      // 调用 patch 函数完成更新
      patch(vnodeToMove, newStartVNode, container)
      // 把 vnodeToMove.el 移动到最前面，即 oldStartVNode.el 的前面
      container.insertBefore(vnodeToMove.el, oldStartVNode.el)
      // 由于旧 children 中该位置的节点所对应的真实 DOM 已经被移动，所以将其设置为 undefined
      prevChildren[idxInOld] = undefined
    } else {
      // 挂载新节点，当双端比对与key查找都不匹配时 newStartVNode 即是新节点
      // newStartVNode 是这轮比较中的“第一个”节点，所以把它挂在到 oldStartVNode 前即可
      mount(newStartVNode, container, false, oldStartVNode.el)
    }
    // 将 newStartIdx 下移一位
    newStartVNode = nextChildren[++newStartIdx]
  }
}
// 挂载没有被处理的全新节点
if (oldEndIdx < oldStartIdx) {
  // 循环结束后当 oldEndIdx < oldStartIdx, 添加新节点
  for (let i = newStartIdx; i <= newEndIdx; i++) {
    mount(nextChildren[i], container, false, oldStartVNode.el)
  }
} else if (newEndIdx < newStartIdx) {
  // 循环结束后当 newEndIdx < newStartIdx, 移除不存在的元素
  for (let i = oldStartIdx; i <= oldEndIdx; i++) {
    container.removeChild(prevChildren[i].el)
  }
}

两端比对 DEMO

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { diff... }

两端比对 - 添加新元素 DEMO

两端比对 - 添加新元素 DEMO2

两端比对 - 移除不存在的元素 DEMO

React.js Diff 算法

updateChildren 大概步骤

1. 初始化最大索引值变量(lastIndex)为 0

2. 遍历新节点数组，初始化是否匹配标识符(find)为 false

   1. 循环旧节点数组，查找 key 相同的节点

      1. 存在，先进行 patch，后判断节点是否需要移动(j<lastIndex)

         1. 需要移动=>移动 DOM
         2. 不需要移动=>更新 lastIndex 变量为当前索引，连接新节点到对应 DOM 上
      2. 不存在，则为新节点，需要挂载 DOM 到上一个新节点的后面

   2. 处理已经不存在的节点

      1. 遍历旧节点数组，移除新节点数组中不存在的节点

updateChildren 代码实现

// 用来存储寻找过程中遇到的旧节点数组中最大索引值
let lastIndex = 0;
// 遍历新的 children
for (let i = 0; i < nextChildren.length; i++) {
  const nextVNode = nextChildren[i];
  let j = 0,
    find = false;
  // 遍历旧的 children
  for (j; j < prevChildren.length; j++) {
    const prevVNode = prevChildren[j];
    // 如果找到了具有相同 key 值的两个节点，则调用 `patch` 函数更新之
    if (nextVNode.key === prevVNode.key) {
      find = true;
      patch(prevVNode, nextVNode, container);
      // 判断节点是否需要移动
      if (j < lastIndex) {
        // 需要移动
        // refNode 是为了下面调用 insertBefore 函数准备的
        const refNode = nextChildren[i - 1].el.nextSibling;
        // 调用 insertBefor 函数移动 DOM，将当前节点的el 移动到 refNode前
        container.insertBefore(prevVNode.el, refNode);
      } else {
        // 更新 lastIndex
        lastIndex = j;
        // 拿到 el 元素，注意这时要让 nextVNode.el 也引用该元素
        const el = (nextVNode.el = prevVNode.el);
      }
      break; // 这里需要 break
    }
    // 挂载新节点
    if (!find) {
      // 找到 refNode
      const refNode =
        i - 1 < 0 ? prevChildren[0].el : nextChildren[i - 1].el.nextSibling;
      mount(nextVNode, container, false, refNode);
    }
  }
  // 移除已经不存在的节点
  // 遍历旧的节点
  for (let i = 0; i < prevChildren.length; i++) {
    const prevVNode = prevChildren[i];
    // 拿着旧 VNode 去新 children 中寻找相同的节点
    const has = nextChildren.find(
      (nextVNode) => nextVNode.key === prevVNode.key
    );
    if (!has) {
      // 如果没有找到相同的节点，则移除
      container.removeChild(prevVNode.el);
    }
  }
}

节点移动、新增、移除 DEMO

Reference

• Vue 渲染器
• Vue的diff算法解析-infoQ