十分详细的diff算法原理解析

patch

比较的第一步就是执行patch，它相当于对比的入口。既然是对比两个虚拟Dom，那么就将两个虚拟Dom作为参数传入patch中。patch的主要作用是对比两个虚拟Dom的根节点，并根据对比结果操作真实Dom。

patch函数的核心代码如下，注意注释。

// updateChildren.js

import patchDetails from "./patchVnode"
import createEle from "./createEle";

/**
 * @description 对比子节点列表并更新真实Dom
 * @param {*} oldCh 旧虚拟Dom子节点列表 
 * @param {*} newCh 新虚拟Dom子节点列表 
 * @param {*} parent 新旧虚拟节点对应的真实Dom
 * @returns 
 */

export default function updateChildren(oldCh, newCh, parent) {
  // 定义四个指针 旧前 旧后 新前 新后 （四个指针两两一对，每一对前后指针所指向的节点以及其之间的节点为未处理的子节点）
  let oldStartIndex = 0;
  let oldEndIndex = oldCh.length - 1;
  let newStartIndex = 0;
  let newEndIndex = newCh.length - 1;

  // 四个指针对应的节点
  let oldStartNode = oldCh[oldStartIndex];
  let oldEndNode = oldCh[oldEndIndex];
  let newStartNode = newCh[newStartIndex];
  let newEndNode = newCh[newEndIndex];

  // oldCh中每个子节点 key 与 index的哈希表 用于四种对比规则都不匹配的情况下在oldCh中寻找节点
  const keyMap = new Map();

  /**
   * 开始遍历两个children数组进行细节对比
   * 对比规则：旧前-新前 旧后-新后 旧前-新后 旧后-新前
   * 对比之后指针进行移动
   * 直到指针不满足以下条件 意味着有一对前后指针之间再无未处理的子节点 则停止对比 直接操作DOM
   */

  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    // 这四种情况是为了让指针在移动的过程中跳过空节点
    if (oldStartNode == undefined) {
      oldStartNode = oldCh[++oldStartIndex];
    } else if (oldEndNode == undefined) {
      oldEndNode = oldCh[--oldEndIndex];
    } else if (newStartNode == undefined) {
      newStartNode = newCh[++newStartIndex];
    } else if (newEndNode == undefined) {
      newEndNode = newCh[--newEndIndex];
    } else if (isSame(oldStartNode, newStartNode)) {
      console.log("method1");
      // 旧前-新前是同一个虚拟节点

      // 两个子节点再对比他们的子节点并更新dom （递归切入点）
      patchDetails(oldStartNode, newStartNode);
      // 指针移动
      oldStartNode = oldCh[++oldStartIndex];
      newStartNode = newCh[++newStartIndex];
    } else if (isSame(oldEndNode, newEndNode)) {
      console.log("method2");
      // 旧后-新后是同一个虚拟节点

      // 两个子节点再对比他们的子节点并更新dom （递归切入点）
      patchDetails(oldEndNode, newEndNode);
      // 指针移动
      oldEndNode = oldCh[--oldEndIndex];
      newEndNode = newCh[--newEndIndex];
    } else if (isSame(oldStartNode, newEndNode)) {
      console.log("method3");
      // 旧前-新后是同一个虚拟节点

      // 两个子节点再对比他们的子节点并更新dom （递归切入点）
      patchDetails(oldStartNode, newEndNode);

      /**
       *  这一步多一个移动(真实)节点的操作
       *  需要把当前指针所指向的子节点 移动到 oldEndIndex所对应真实节点之后（也就是未处理真实节点的尾部）
       *  注意：这一步是在操作真实节点
       */
      parent.insertBefore(oldStartNode.elm, oldEndNode.elm.nextSibling);

      // 指针移动
      oldStartNode = oldCh[++oldStartIndex];
      newEndNode = newCh[--newEndIndex];
    } else if (isSame(oldEndNode, newStartNode)) {
      console.log("method4");
      // 旧后-新前 是同一个虚拟节点

      // 两个子节点再对比他们的子节点并更新dom （递归切入点）
      patchDetails(oldEndNode, newStartNode);
      /**
       *  这一步多一个移动(真实)节点的操作
       *  与method3不同在移动位置
       *  需要把当前指针所指向的子节点 移动到 oldStartIndex所对应真实节点之前（也就是未处理真实节点的顶部）
       *  注意：这一步是在操作真实节点
       */
      parent.insertBefore(oldEndNode.elm, oldCh[oldStartIndex].elm);

      // 指针移动
      oldEndNode = oldCh[--oldEndIndex];
      newStartNode = newCh[++newStartIndex];
    } else {
      console.log("does not match");
      // 四种规则都不匹配

      // 生成keyMap
      if (keyMap.size == 0) {
        for (let i = oldStartIndex; i <= oldEndIndex; i++) {
          if (oldCh[i].key) keyMap.set(oldCh[i].key, i);
        }
      }

      // 在oldCh中搜索当前newStartIndex所指向的节点
      if (keyMap.has(newStartNode.key)) {
        // 搜索到了

        // 先获取oldCh中该虚拟节点
        const oldMoveNode = oldCh[keyMap.get(newStartNode.key)];
        // 两个子节点再对比他们的子节点并更新dom （递归切入点）
        patchDetails(oldMoveNode, newStartNode);

        // 移动这个节点（移动的是真实节点）
        parent.insertBefore(oldMoveNode.elm, oldStartNode.elm);

        // 该虚拟节点设置为undefined（还记得最开始的四个条件吗，因为这里会将子节点制空，所以加了那四个条件）
        oldCh[keyMap.get(newStartNode.key)] = undefined;
          
      } else {
        // 没搜索到 直接插入
        parent.insertBefore(createEle(newStartNode), oldStartNode.elm);
      }

      // 指针移动
      newStartNode = newCh[++newStartIndex];
    }
  }

  /**
   * 插入和删除节点
   * while结束后 有一对前后指针之间仍然有未处理的子节点，那么就会进行插入或者删除操作
   * oldCh的双指针中有未处理的子节点，进行删除操作
   * newCh的双指针中有未处理的子节点，进行插入操作
   */
  if (oldStartIndex <= oldEndIndex) {
    // 删除
    for (let i = oldStartIndex; i <= oldEndIndex; i++) {
      // 加判断是因为oldCh[i]有可能为undefined
      if(oldCh[i]) parent.removeChild(oldCh[i].elm);
    }
  } else if (newStartIndex <= newEndIndex) {
    /**
     * 插入
     * 这里需要注意的点是从哪里插入，也就是appendChild的第二个参数
     * 应该从oldStartIndex对应的位置插入
     */
    for (let i = newStartIndex; i <= newEndIndex; i++) {
      // oldCh[oldStartIndex]存在是从头部插入
      parent.insertBefore(createEle(newCh[i]), oldCh[oldStartIndex] ? oldCh[oldStartIndex].elm : undefined);
    }
  }
}

// 判断两个虚拟节点是否为同一个虚拟节点
function isSame(a, b) {
  return a.sel == b.sel && a.key == b.key;
}